【数据结构初阶】《排序（插入，选择，交换，归并，计数排序）》---详解

j7～

489人浏览 · 2026-08-23 12:55:35

j7～ · 2026-08-23 12:55:35 发布

一.排序的概念及其应用

1.概念

排序：所谓排序，就是使⼀串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假设待排序记录序列里有多条关键字相同的记录，如果排序完成后，这类记录的相对先后顺序不发生改变；也就是原序列中 r [i] = r [j]，且 r [i] 位于 r [j] 前面，排序之后 r [i] 依旧处在 r [j] 之前，该排序算法就是稳定的，反之则为不稳定排序。
内部排序：所有待排序的数据元素完全存储在内存当中进行的排序。
外部排序：待处理的数据量过大，无法全部装入内存，排序过程中需要在内存与外存之间来回移动数据完成的排序。

2.运用

比如说：购物筛选排序

院校排名

3.常见的排序算法

二.实现常见排序算法

首先开始的是插入排序：

1. 插入排序

基本思想：

直接插入排序是⼀种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到⼀个已经排好序的有序序列中，直到所有的记录插入完为止，得到⼀个新的有序序列。

实际中我们玩扑克牌时，就⽤了插入排序的思想

a.直接插入排序：`

当插入第 i(i>=1) 个元素时，前⾯的 array[0],array[1],…,array[i-1] 已经排好序，此用 array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移。

图示：

代码如下：

void InsertSort(int* a, int n)
{
    assert(a);
	for (int i = 0; i < n - 1; ++i)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

如果tmp < a[end]，代表 tmp 应该放在 a [end] 的前面，就把 a [end] 向后挪到 end+1 的位置，再 end 自减继续向前比较；

如果 tmp 大于等于 a [end]，说明找到了插入位置，直接跳出 while 循环；

while 循环结束有两种情况：end 变成‑1，代表 tmp 比有序区间所有元素都小；或者遇到第一个小于等于 tmp 的元素。两种情况插入下标都是end+1，执行a[end + 1] = tmp，把待插入元素放到正确位置，本轮插入完成。

完整代码：

#include<stdio.h>
#include<assert.h>
void InsertSort(int* a, int n)
{
	assert(a);
	for (int i = 0; i < n - 1; ++i)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}


void TestInsertSort()
{
	int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
	InsertSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main()
{
	TestInsertSort();
	return 0;
}

（1）冒泡排序属于原地排序算法吗？

冒泡排序过程中仅借助少量临时变量完成元素交换，不需要额外开辟数组来存储排序数据，空间复杂度为O(1)，由此可见冒泡排序是原地排序算法。

（2）冒泡排序是稳定排序算法吗？

冒泡排序的交换条件是前一个元素大于后一个相邻元素才进行交换；若两个元素的关键字相等，则不会触发交换操作，相等元素原本的相对先后次序能够得以保留，因此冒泡排序是稳定的排序算法。

（3）冒泡排序的时间复杂度如何？

引入 flag 标志做优化后，倘若待排序数组本身已经全部有序，第一轮遍历不会产生任何交换操作，算法直接提前结束，此时对应的最好时间复杂度为 O(n)。若是数组完全逆序，每一轮冒泡都要执行多次元素交换，必须完整跑完全部 (n‑1)轮排序流程，最坏时间复杂度达到 O(n^2)。每一轮冒泡平均需要执行 n 次对比，一共执行 n 轮遍历，所以冒泡排序的平均时间复杂度为 O(n^2)。

冒泡排序的特性总结：

数组有序度越高，经过 flag 优化后的冒泡排序性能越好，完全有序时可以直接提前结束排序流程。
时间复杂度：最优 O(n)，最差O(n^2)，平均 O(n^2)。
空间复杂度：O(1)，属于原地的内部排序。
稳定性：稳定排序。

b.希尔排序（ShellSort）

希尔排序法又称缩⼩增量法。希尔排序法的基本思想是：先选定⼀个整数（通常是gap = n/3+1），把待排序文件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进⾏排序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进⾏插⼊排序，当gap=1时，就相当于直接插⼊排序。
它是在直接插⼊排序算法的基础上进⾏改进⽽来的，综合来说它的效率肯定是要⾼于直接插⼊排序算法的。

代码如下：

// 希尔排序
void ShellSort(int* a, int n)
{
    assert(a);  // 确保传入的指针不为空

    int gap = n;  // gap为间隔，初始设为数组长度

    // 外层循环：控制gap的递减，当gap>1时继续排序
    // 时间复杂度：O(log₃n)（以3为底的对数）
    while (gap > 1)  // gap始终>=1，所以不能写成gap>0，否则会死循环
    {
        gap = gap / 3 + 1;  // gap每次缩小为原来的1/3，+1保证最后一次gap=1
        // gap = gap / 2;   // 也可以每次缩小一半，两种写法都可以

        // 内层循环：对所有组进行插入排序
        // 时间复杂度：O(n)
        for (int i = 0; i < n - gap; ++i)
        {
            int end = i;              // end指向当前组中已排序部分的最后一个元素
            int tmp = a[end + gap];   // tmp保存待插入元素的值

            // 在组内进行插入排序，将tmp插入到正确位置
            while (end >= 0)
            {
                if (tmp < a[end])     // 待插入元素比当前元素小
                {
                    a[end + gap] = a[end];  // 当前元素往后移
                    end -= gap;             // 继续往前比较同组的前一个元素
                }
                else
                {
                    break;            // 找到正确位置，跳出循环
                }
            }
            a[end + gap] = tmp;       // 将tmp插入到正确位置
        }
    }
}

这个代码主要干了三步：

分组：每隔gap个位置的元素归为一组（相当于跳着分）

预排序：对每组分别进行插入排序，让小的元素快速往前跑，大的元素快速往后跑

缩小gap：不断缩小gap，让分组越来越细，直到gap=1时相当于普通插入排序

这里给大家讲一下，gap的取值：

希尔本人最初给出的增量方案是 gap = n / 2，每完成一轮分组排序之后，就将增量折半更新，也就是gap = gap / 2，一直循环到 gap = 1。当 gap 等于 1 的时候，此时的排序就退化成普通的直接插入排序。

后来 Knuth 提出了另一种增量公式：gap = (gap / 3) + 1，每一轮把增量变为原来的三分之一。这里加 1 是做了防护处理，如果不加，当gap <=3时，gap/3运算结果就会得到 0，增量变成 0 之后排序直接出错，无法走到 gap=1 这一步，也就不能完成最后的插入排序。

选用 gap = (gap / 3) + 1 的 Knuth 增量，整体表现会更加稳定，可以有效降低比较与交换的总次数，提升希尔排序运行效率。按照这种规则不断缩小增量，能够对数组做更合理的分组。每一轮都会把数组切分成若干个子序列，对每一组子序列执行插入排序。在排序前期，大的 gap 可以让小元素快速挪到数组靠前位置，同时把大元素尽快向后挪动，以此减少后面轮次需要做的比较和交换操作。

希尔排序特性总结：

希尔排序是直接插入排序的优化。gap>1为预排序，让数组趋近有序；gap=1退化为直接插入排序，此时数组接近有序，排序速度快，以此实现整体优化，可与直接插入排序做性能对比测试。
时间复杂度：受 gap 增量序列影响难以精确计算，Knuth 增量下约 O(N^(1.3)），最坏可达 O(n^2)。
空间复杂度：O(1)，原地内部排序。
稳定性：不稳定。分组操作会改变相等元素原有相对位置。
适合中等规模数据，数组越接近有序效率越高。

希尔排序时间复杂度不好计算，因为 gap 的取值很多，导致很难去计算，因此很多书中给出的希尔排序的时间复杂度都不固定。《数据结构(C语⾔版)》--- 严蔚敏书中给出的时间复杂度为：

2.选择排序

选择排序的基本思想：

每⼀次从待排序的数据元素中选出最小（或最大）的⼀个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

a.直接选择排序

1. 在元素集合 array[i] -- array[n-1] 中选择关键码最大(小)的数据元素
2. 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
3. 在剩余的 array[i] -- array[n-2]（array[i+1] -- array[n-1]）集合中，重复上述步
骤，直到集合剩余 1 个元素

代码如下：

// 交换两个整数的值
void Swap(int* p1, int* p2)
{
    int tmp = *p1;  // 临时保存p1指向的值
    *p1 = *p2;      // 将p2指向的值赋给p1
    *p2 = tmp;      // 将临时保存的值赋给p2
}

// 选择排序（升序）
void SelectSort(int* a, int n)
{
    assert(a);  // 确保传入的指针不为空

    int begin = 0;  // begin表示当前未排序部分的起始位置
    while (begin < n)  // 当begin还没到数组末尾时继续
    {
        int mini = begin;  // 假设当前位置的元素是最小的
        
        // 在未排序部分中查找最小元素的下标
        for (int i = begin; i < n; i++)
        {
            if (a[i] < a[mini])  // 如果找到更小的元素
            {
                mini = i;  // 更新最小元素的下标
            }
        }
        
        // 将找到的最小元素交换到未排序部分的最前面
        Swap(&a[begin], &a[mini]);
        
        begin++;  // 已排序部分向后扩展一位
    }
}

优化后的版本：

// 优化后的代码：(一次选出两个数)
void Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

// 直接选择排序（优化版：同时选最小和最大）
void SelectSort(int* a, int n)
{
    assert(a);

    int begin = 0, end = n - 1;  // begin指向未排序部分的头，end指向未排序部分的尾
    while (begin < end)          // 当begin和end相遇或错过时结束（奇数个会相遇，偶数个会错过）
    {
        int mini = begin, maxi = begin;  // 假设最小值和最大值都在begin位置
        
        // 遍历未排序部分，同时找出最小值和最大值的下标
        for (int i = begin + 1; i <= end; ++i)  // 从begin+1开始，因为begin已经假设为最值
        {
            if (a[i] < a[mini])   // 找到更小的，更新mini
            {
                mini = i;
            }
            if (a[i] > a[maxi])   // 找到更大的，更新maxi
            {
                maxi = i;
            }
        }
        
        // 第一步：把最小值放到begin位置
        Swap(&a[begin], &a[mini]);

        // 关键修正：如果begin和maxi重叠，说明最大值原本在begin位置
        // 但上面的Swap已经把begin位置的值换到了mini位置
        // 所以最大值现在在mini位置，需要更新maxi
        if (begin == maxi)
        {
            maxi = mini;
        }
        
        // 第二步：把最大值放到end位置
        Swap(&a[end], &a[maxi]);
        
        // 缩小未排序区间
        ++begin;
        --end;
    }
}

（1）选择排序是原地排序算法吗？

选择排序仅使用常数级别的临时变量，空间复杂度为 \(O(1)\)，属于原地排序算法。

（2）选择排序是稳定的排序算法吗？

选择排序是不稳定的排序算法。它每一轮在未排序区间查找最小值，再把最小值和未排序区间的首位元素交换，交换操作会打乱相等元素原本的相对次序。举个例子，数组4，9，4，1，8，第一轮选出最小值 1，和第一个 4 交换，原来靠前的 4 就被换到第二个 4 的后方，相等元素顺序被破坏，因此不具备稳定性。

（3）选择排序的时间复杂度是多少？

即便做了优化，选择排序最好情况下依旧需要完整遍历查找最小值，时间复杂度还是 \O(n^2)，最坏与平均时间复杂度同样为 O(n^2)。

直接选择排序的特性总结：算法整体效率较差，实际开发场景很少用到，一般不推荐使用。

时间复杂度：O(N^2)。
空间复杂度：O(1)。
稳定性：不稳定。

b.堆排序（HeapSort）

这里给大家简单介绍，具体相关的内容看这个：

【数据结构初阶】《堆（Heap)》---详解-CSDN博客

堆排序（Heapsort）是借助堆这种完全二叉树结构实现的排序算法，属于选择排序的改良版本，依靠堆结构完成最值的选取。需要重点记住：数组排升序要构建大堆，数组排降序要构建小堆。

// 交换两个整数的值
void Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

// 向下调整算法：将parent位置的元素向下调整，使其满足大堆的性质
// a: 数组首地址，size: 堆的大小，parent: 需要向下调整的节点下标
void AdjustDown(int* a, int size, int parent)
{
    // 默认左孩子为较大的孩子
    int child = parent * 2 + 1;  // 计算左孩子下标
    
    // 如果孩子存在，就继续调整
    while (child < size)
    {
        // 选出左右孩子中较大的那个
        // 条件：右孩子存在（child+1 < size）并且右孩子比左孩子大
        if (child + 1 < size && a[child + 1] > a[child])
        {
            ++child;  // child指向右孩子
        }
        
        // 如果孩子比父亲大，交换并继续向下调整
        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);  // 交换父子
            parent = child;  // 更新父亲下标为原来孩子的位置
            child = parent * 2 + 1;  // 重新计算左孩子下标，继续向下调整
        }
        else
        {
            break;  // 孩子不比父亲大，调整结束
        }
    }
}

// 堆排序（升序）
void HeapSort(int* a, int n)
{
    assert(a);  // 确保传入的指针不为空

    // 第一步：建堆（从下往上，依次调整所有非叶子节点）
    // (n-1)是最后一个叶子节点的下标，((n-1)-1)/2是其父亲节点的下标
    // 从最后一个非叶子节点开始，一直调整到根节点
    for (int i = ((n - 1) - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);  // 以i为根，向下调整建堆
    }

    // 第二步：排序（升序用大堆）
    int end = n - 1;  // end指向堆中最后一个元素的下标
    while (end > 0)   // 当堆中还有元素时
    {
        // 将堆顶元素（最大值）和堆中最后一个元素交换
        Swap(&a[0], &a[end]);
        
        // 交换后，end位置的元素已经排好序，不再参与堆结构调整
        // 对新的堆顶（0）进行向下调整，恢复大堆结构
        // 注意：此时堆的大小为end，因为end位置的元素已经排好了
        AdjustDown(a, end, 0);
        
        --end;  // 堆的大小减1，继续排下一个
    }
}

a. 堆排序是原地排序算法吗？

堆排序只使用少量临时变量完成交换与调整，不需要额外开辟数组，空间复杂度 \(O(1)\)，属于原地排序算法。

b. 堆排序是稳定的排序算法吗？

堆排序是不稳定排序。堆顶和堆尾直接交换元素的操作，会打乱关键字相等元素原本的先后相对顺序，无法维持稳定性。

c. 堆排序的时间复杂度是多少？

建堆时间复杂度 O(n)；每一次向下调整的时间复杂度 O(log n)，一共要执行 n 次调整。最好、最坏、平均时间复杂度均为 O(nlog n)。

直接选择排序的特性总结：

堆排序使用堆来选数，效率就高了许多。
时间复杂度：O(N*logN)。
空间复杂度：O(1)。
稳定性：不稳定。

特点：对数据有序度不敏感，无论原始数组有序还是逆序，时间复杂度都保持 O(n*log n)。

3.交换排序

交换排序基本思想：

所谓交换，就是根据序列中两个记录键值的⽐较结果来对换这两个记录在序列中的位置
交换排序的特点是：将键值较⼤的记录向序列的尾部移动，键值较⼩的记录向序列的前部移动

a.冒泡排序

前面在C语言中我们已经接触过冒泡排序的思路了，冒泡排序是⼀种最基础的交换排序。之所以叫做冒泡排序，因为每⼀个元素都可以像小气泡⼀样，根据自身大小⼀点⼀点向数组的⼀侧移动。

初始数组：[4, 5, 6, 3, 2, 1]

1. 比较 a[0]与a[1]：4 和 5，4＜5，不交换，数组：[4, 5, 6, 3, 2, 1]
2. 比较 a[1]与a[2]：5 和 6，5＜6，不交换，数组：[4, 5, 6, 3, 2, 1]
3. 比较 a[2]与a[3]：6 和 3，6＞3，交换，数组：[4, 5, 3, 6, 2, 1]
4. 比较 a[3]与a[4]：6 和 2，6＞2，交换，数组：[4, 5, 3, 2, 6, 1]
5. 比较 a[4]与a[5]：6 和 1，6＞1，交换，数组：[4, 5, 3, 2, 1, 6]
第一趟冒泡结束，本趟将数组最大值 6 冒泡到数组末尾a[5]位置

可以看出，经过一次冒泡操作之后，6 这个元素已经存储在正确的位置上。要想完成所有数据的排序，我们只要进行 6 次这样的冒泡操作就行了。

初始状态：[4, 5, 6, 3, 2, 1]
第 1 次冒泡：[4, 5, 3, 2, 1, 6]，最大值 6 已经排到末尾
第 2 次冒泡：[4, 3, 2, 1, 5, 6]，次大值 5 排好
第 3 次冒泡：[3, 2, 1, 4, 5, 6]，4 排好
第 4 次冒泡：[2, 1, 3, 4, 5, 6]，3 排好
第 5 次冒泡：[1, 2, 3, 4, 5, 6]，2 排好
第 6 次冒泡：[1, 2, 3, 4, 5, 6]，整体有序
数组长度为 6，最多需要进行n‑1=5趟冒泡，第 6 趟实际已经全部有序。如果加上 flag 标记，检测到本趟没有发生交换就可以直接提前结束排序。

#include <stdio.h>

void PrintArray(int a[], int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void BubbleSort(int a[], int n)
{
	int i, j;
	for (i = 0; i < n; i++)
	{
		int flag = 1; //标记本趟是否已经全部有序
		for (j = 0; j < n - i - 1; j++)
		{
			if (a[j] > a[j + 1])
			{
				int tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
				flag = 0;
			}
		}
		if (flag == 1)
		{
			break; //本趟没有交换，数组已经有序，直接退出
		}
	}
}

void TestBubbleSort()
{
	int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
	BubbleSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main()
{
	TestBubbleSort();
	return 0;
}

（1）冒泡排序是原地排序算法吗？

冒泡排序仅做相邻元素交换，只用到常数大小临时变量，空间复杂度为 \(O(1)\)，属于原地排序算法，不需要额外开辟数组空间。

（2）冒泡排序是稳定的排序算法吗？

冒泡排序是稳定排序算法。算法中只有发生交换才会改动元素相对位置；当相邻两个元素值相等时，我们不执行交换，等值元素的先后次序就不会被破坏，因此可以维持稳定性。

（3）冒泡排序的时间复杂度是多少？

最好情况：数组本身已经完全有序，借助 flag 标记只需一趟遍历即可结束，时间复杂度 O(n)。 最坏情况：数组完全逆序，需要执行完整的 n 趟冒泡，时间复杂度 O(n^2)。平均情况下时间复杂度同样为 O(n^2)，数据量变大后效率下降明显。

（4）冒泡排序与插入排序相比哪个更好？

二者最好、最坏时间复杂度一致。但数据接近有序时，插入排序整体性能优于冒泡排序。举个例子数组1 2 3 5 4 6，冒泡排序要执行(N‑1)+(N‑2)次比较；插入排序仅需要 N 次比较。冒泡即使检测到有序，也会存在多余的遍历开销；同时冒泡交换次数会比插入排序更多。

冒泡排序的特性总结：

逻辑简单易懂，是入门级排序算法，但不适合大规模数据。
时间复杂度：O(N^2)。
空间复杂度：O(1)。
稳定性：稳定。特点：可以通过 flag 标记优化，数组有序时提前终止排序。

b.快速排序法（Quicksort）

快速排序是Hoare于1962年提出的⼀种二叉树结构的交换排序⽅法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左⼦序列中所有元素均小于基准值，右子序列中所有元素均⼤于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

由图可知：快排的处理过程是由上到下 的，先分区，然后再处理子问题。

快速排序实现主框架：

//快速排序
void QuickSort(int* a, int left, int right)
{
	if (left >= right) {
		return;
	}
	//_QuickSort⽤于按照基准值将区间[left,right)中的元素进⾏划分
	int meet = _QuickSort(a, left, right);
	QuickSort(a, left, meet - 1);
	QuickSort(a, meet + 1, right);
}

快速排序的递归逻辑和二叉树前序遍历十分类似。大家在写快排递归框架的时候，可以借鉴二叉树前序遍历的思路来快速搭建代码：先对当前区间完成处理，之后再递归处理左右子区间。把整体框架写好后，核心工作就是实现划分函数，依据基准值完成区间内元素的分区操作。

拓展：

快速排序：当前区间划分 --> 递归左区间 --> 递归右区间
二叉树前序遍历：访问根节点 --> 递归左子树 --> 递归右子树两者都是先处理当前部分，再递归处理左右两边，递归结构是相同的。

将区间中的元素进⾏划分的 _QuickSort ⽅法主要有以下几种实现方式：

a.hoare版本

算法思路：
(1）创建左右指针，确定基准值
(2）从右向左找出⽐基准值小的数据，从左向右找出比基准值⼤的数据，左右指针数据交换，进⼊下次循环

问题1：为什么跳出循环后right位置的值⼀定不⼤于key？

当 left > right 时，即right⾛到left的左侧，⽽left扫描过的数据均不⼤于key，因此right此时指
向的数据⼀定不⼤于key

问题2：为什么left 和 right指定的数据和key值相等时也要交换？

当数组存在大量重复元素时，如果遇到与 key 相等的元素就停止移动，会造成划分失效，递归区间无法有效缩小，快速排序时间复杂度退化到O(n^2)。让等于 key 的数据参与交换，保证分区正常分割；虽然会带来少量额外交换开销，但避免最坏情况。

回答图片中的问题：

必须跳出循环。 当left == right，两指针相遇，该位置就是基准 key 的最终落点，再继续移动指针会越界，划分逻辑失效，所以要结束循环，把 key 放到相遇位置。

代码如下：

//交换两个整型变量的值，传入指针实现实参修改
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

// Hoare版本快排划分函数
// a：待排序数组，begin：区间左边界，end：区间右边界
// 返回值：基准元素最终所在的下标位置
int PartSort1(int* a, int begin, int end)
{
	//左右指针分别指向区间首尾
	int left = begin, right = end;
	//选择区间最左侧元素作为基准值，keyi保存基准值下标
	int keyi = left;

	//left和right没有相遇时循环继续
	while (left < right)
	{
		//右边指针先走，向前找比基准值小的元素（升序）
		//>=：遇到等于基准的元素直接跳过，保证算法稳定性相关逻辑
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
	
		//左边指针向后走，找比基准值大的元素
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		//左右指针都找到目标元素，交换两者位置
		Swap(&a[left], &a[right]);
	}	
	//left与right相遇，把基准元素交换到相遇点，基准归位
	Swap(&a[keyi], &a[left]);
	//更新基准下标为相遇位置
	keyi = left;
 
	return keyi; //返回基准的位置，用于递归划分左右子区间
}

小细节：这里的 while 要加等号的原因是避免出现死循环的情况。

b.挖坑法

思路：
创建左右指针。⾸先从右向左找出⽐基准⼩的数据，找到后⽴即放⼊左边坑中，当前位置变为新的"坑"，然后从左向右找出⽐基准⼤的数据，找到后⽴即放⼊右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放⼊当前的"坑"中，返回当前"坑"下标（即分界值下标）

// 挖坑法快速排序划分函数
// a：待排序数组，begin：区间左边界，end：区间右边界
// 返回值：基准元素最终存放的下标
int PartSort2(int* a, int begin, int end)
{
	int key = a[begin];	//保存基准值，把begin位置挖出第一个坑
	int pt = begin;		//piti记录坑的下标，初始坑在最左侧

	while (begin < end)	//左右指针未相遇，循环进行挖坑填坑
	{
		// 右边找小，填到左边的坑里面去。这个位置形成新的坑
		while (begin < end && a[end] >= key)
		{
			--end;	//从右向左，找比基准key小的元素
		}
		a[pt] = a[end];	//将找到的较小元素填入坑中
		pt = end;			//原end位置变为新的坑

		// 左边找大，填到右边的坑里面去。这个位置形成新的坑
		while (begin < end && a[begin] <= key)
		{
			++begin;	//从左向右，找比基准key大的元素
		}
		a[pt] = a[begin];	//将找到的较大元素填入当前坑
		piti = begin;		//原begin位置更新为新坑
	}
	a[pt] = key;	//begin与end相遇，把基准值key填入最后的坑中，基准归位
	return pt;	//返回基准元素的下标，用于递归划分左右区间
}

注意：如果在 while 循环中去掉等号，把 a[end] >= key 修改为 a[end] > key，同时把 a[begin] <= key 修改为 a[begin] < key。当数组中存在大量与基准key相等的元素时，指针遇到等于 key 的元素就会停下，会把等值元素分散到左右两个区间内，无法实现左边全部≤key，右边全部≥key的划分效果。因此挖坑法中需要保留>=与<=中的等号，遇到等于基准的元素继续移动指针，保证划分后左区间全部小于等于基准、右区间全部大于等于基准，让等值元素尽量聚集，优化递归划分效率。

c.lomuto前后指针

设置两个同向指针prev、cur，选最左边元素当基准key。 prev初始在基准处，cur从下一个位置向后遍历：

cur遇到比key小的元素：prev后移一位，交换prev和cur，再cur++；
cur遇到大于等于key的元素：只让cur++，prev不动。

cur遍历结束后，交换基准与prev位置元素，那prev就是基准的正确下标了，再递归处理左右区间。

特点：两个指针从左向右走，方便链表实现快排。

对比：Hoare、挖坑是双向对向指针；前后指针为同向指针。

代码如下：

// 前后指针法 快速排序划分函数
// a：待排序数组，begin、end：当前区间左右边界
// 返回基准元素最终的下标
int PartSort3(int* a, int begin, int end)
{
	int prev = begin;	// prev：小于基准区域的末尾下标
	int cur = begin + 1;// cur：探测指针，从基准下一位开始向后扫描
	int keyi = begin;	// keyi：基准元素下标

	// 加入三数取中的优化，避免有序数组下快排退化O(n²)
	//int midi = GetMidIndex(a, begin, end);
	//Swap(&a[keyi], &a[midi]);

	while (cur <= end)	// cur遍历到区间末尾结束
	{
		// 如果cur指向元素小于基准，prev先++；prev不等于cur才交换，避免自己和自己交换
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		++cur;	//cur无论是否交换都向后走
	}
	// 遍历完成，把基准交换到prev位置，基准归位
	Swap(&a[prev], &a[keyi]);
	keyi = prev;

	return keyi;	//返回基准下标，用于递归划分左右区间
}

注意：如果将 if 里面的条件改为 a[cur] <= a[keyi]，虽然不会导致排序结果出错，但是可能会改变相等元素的相对顺序，所以还是应该写成 a[cur] < a[keyi]，不要加上等号。

d.快速排序优化 --- 三数取中法

（1）定义：

就是取数组的第一个元素、最后一个元素、中间位置元素，三个数比一比，挑出大小排在中间的那个作为基准值（pivot）。这样做能让选出来的基准不会太极端，避免快排划分的时候一边倒。

（2）用处

避免最坏情况
快排最怕每次选到的基准都是最大或最小的，这样划分完一边全是元素，另一边是空的，时间复杂度直接变成 O(n²)。三数取中法能大大降低这种倒霉情况的发生概率。

让划分更均匀
基准值越靠近中间值，左右两边就越均衡，递归深度浅了，比较和交换的次数也就少了，效率自然上来了。

对付有序数组更友好
如果数组本来就已经排好序了，固定选第一个元素做基准的话，每次划分都是空的，直接拉胯。三数取中法在这种情况下能选到一个中间大小的元素，就不会那么惨了。

总的来说，三数取中法通过选择合适的中间元素，可以减少最坏情况的发生，提高划分的平衡性和效率，从而提高排序算法的整体效率。

// 三数取中法：获取 begin、mid、end 三者中间值元素的下标
// 目的：避免有序数组选到极值当基准，防止快排时间复杂度退化到 O(n²)
int	GetMidIndex(int* a, int begin, int end)
{
	//int mid = (begin + end) / 2;  // begin+end 过大时会发生整数溢出
    int mid = begin + (end - begin) / 2; // 防溢出写法，等价于 (begin+end)/2
 
	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
		{
			return mid;	// begin < mid < end，中间值为mid
		}
		else if (a[begin] < a[end])
		{
			return end;	// begin < end <= mid，中间值为end
		}
		else
		{
			return begin; // end <= begin < mid，中间值为begin
		}
	}
	else // a[begin] >= a[mid]
	{
		if (a[mid] > a[end])
		{
			return mid;	// end < mid <= begin，中间值为mid
		}
		else if (a[begin] < a[end])
		{
			return begin; // mid <= begin < end，中间值为begin
		}
		else
		{
			return end;	// mid <= end <= begin，中间值为end
		}
	}
}

三数取中法选 key。
递归到小的子区间时，可以考虑使用插入排序。

优化后的代码：

void Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

// Hoare 版本的快速排序单趟排序
// 返回值 keyi 是基准值最终所在的位置
int PartSort1(int* a, int begin, int end)
{
    int left = begin, right = end;   // left指向左边界，right指向右边界
    int keyi = left;                 // keyi记录基准值的下标，初始为左边第一个

    // 加入三数取中的优化
    int midi = GetMidiIndex(a, begin, end);  // 从begin、end、中间位置选出中间值的下标
    Swap(&a[keyi], &a[midi]);                // 把中间值交换到begin位置作为基准

    // 当left和right没有相遇时，继续划分
    while (left < right)
    {
        // 右边先走，找比基准值小的数 -- 升序排列
        // 注意：left<right是防止越界，a[right]>=a[keyi]是跳过大于等于基准的值
        while (left < right && a[right] >= a[keyi])
        {
            --right;  // 当前值比基准大或相等，继续向左移动
        }

        // 左边再走，找比基准值大的数
        while (left < right && a[left] <= a[keyi])
        {
            ++left;  // 当前值比基准小或相等，继续向右移动
        }

        // 交换左边找到的大数和右边找到的小数
        Swap(&a[left], &a[right]);
    }

    // 循环结束后，left和right相遇，这个位置就是基准值最终应该放的位置
    // 将基准值交换到相遇位置
    Swap(&a[keyi], &a[left]);
    keyi = left;  // 更新基准值的下标

    return keyi;  // 返回基准值的最终位置，方便递归划分左右子区间
}

// 挖坑法快速排序划分函数
// a：待排序数组，begin、end：当前区间左右边界
// 返回值：基准元素最终存放的下标
int PartSort2(int* a, int begin, int end)
{
	int key = a[begin];
	int piti = begin;

    // 加入三数取中的优化：选出三者中间值，交换到基准位置，避免有序数组性能退化
	int midi = GetMidIndex(a, begin, end);
	Swap(&a[begin], &a[midi]);

	key = a[begin];   //交换后要重新更新保存基准值
	piti = begin;     //坑位同步重置

	while (begin < end)
	{
		// 右边找小，填到左边的坑里面去。这个位置形成新的坑
		while (begin < end && a[end] >= key)
		{
			--end;
		}
		a[piti] = a[end]; // 将找到的较小值填入当前坑
		piti = end;       // end位置变为新坑

		// 左边找大，填到右边的坑里面去。这个位置形成新的坑
		while (begin < end && a[begin] <= key)
		{
			++begin;
		}
		a[piti] = a[begin]; // 将找到的较大值填入当前坑
		piti = begin;       // begin位置更新为新坑
	}
	a[piti] = key; // begin与end相遇，把基准key填入最后的坑中，基准归位
	return piti;   // 返回基准下标，用于递归划分左右子区间
}

//交换两个整型，传入指针修改原数组元素
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
// 前后指针法 快排划分
// a：数组，begin、end：当前区间左右下标
// 返回：基准元素排序完成后的下标
int PartSort3(int* a, int begin, int end)
{
	int prev = begin;	// prev：小于基准元素区域的末尾下标
	int cur = begin + 1;// cur：探测指针，从基准下一位向后扫描
	int keyi = begin;	// keyi：基准元素的下标

	// 加入三数取中的优化，防止有序数组快排退化O(n²)
	//int midi = GetMidIndex(a, begin, end);
	//Swap(&a[keyi], &a[midi]);
 
	while (cur <= end)	// cur遍历到区间末尾结束循环
	{
		// 如果cur指向元素小于基准，prev先自增；prev不等于cur才交换，避免自身交换
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		++cur; //cur无论是否交换都向后移动
	}
	// 遍历结束，把基准交换到prev位置，基准归位
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
 
	return keyi; //返回基准下标，用于递归划分左右子区间
}

快速排序是效率很高的排序算法，处理大批量数据的时候性能很好。不过当递归出来的区间比较小的时候，快排的速度就会慢下来。主要原因是递归调用会带来额外的开销，对于很小的数组区间来说，这部分开销占比会比较大，这个时候插入排序反而会更快。插入排序虽然时间复杂度是O(n^2)，但它的常数因子比较小，缓存局部性也不错，处理小规模数据效果很好。

所以我们可以给快速排序加一个优化：如果递归得到的区间长度小于设定阈值，就不再继续递归快排，直接使用插入排序。这样既减少了递归调用带来的开销，又发挥出插入排序处理小区间的优势，整体的排序效率就能得到提升。一般阈值取 10~20 就可以，不需要设置得特别严格。

代码如下：

#include <stdio.h>

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

int	GetMidIndex(int* a, int begin, int end)
{
	int mid = begin + (end - begin) / 2;

	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
		{
			return mid;
		}
		else if (a[begin] < a[end])
		{
			return end;
		}
		else
		{
			return begin;
		}
	}
	else
	{
		if (a[mid] > a[end])
		{
			return mid;
		}
		else if (a[begin] < a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
}

//前后指针划分 PartSort3
int PartSort3(int* a, int begin, int end)
{
	int prev = begin;
	int cur = begin + 1;
	int keyi = begin;

	int midi = GetMidIndex(a, begin, end);
	Swap(&a[keyi], &a[midi]);

	while (cur <= end)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		++cur;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;

	return keyi;
}

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; ++i)
	{
		// [0,end]有序，把end+1位置的值插入，保持有序
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end]) // 升序
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}




//打印数组
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

// 快速排序（递归）
void QuickSort(int* a, int begin, int end)
{

	// 区间不存在，或者只有一个值则不需要再处理
	if (begin >= end)
	{
		return;
	}

	if (end - begin > 10)
	{
		int keyi = PartSort3(a, begin, end);

		// [begin, keyi-1] keyi [keyi+1, end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	else // 递归到小的子区间时，可以考虑使用插入排序
	{
		InsertSort(a + begin, end - begin + 1);
	}
}

void TestQuickSort()
{
	int a[] = { 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 };
	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main()
{
	TestQuickSort();
	return 0;
}

e.快速排序非递归

原理：

递归快排依靠系统栈，在数组完全有序这种极端场景，递归深度等于数组长度，系统栈空间不足，发生栈溢出。非递归快排使用自己创建的栈（堆上的栈结构）模拟递归过程，把待处理的[begin,end]区间保存到栈；时间复杂度不变，避免系统栈溢出风险。

栈是后进先出：先压右区间，再压左区间，出栈顺序等价递归的前序遍历。

将初始区间[begin, end]入栈
栈不为空就循环：
出栈一个待排序区间[left, right]
调用划分函数PartSort3得到基准下标keyi，完成单趟快排
如果右子区间有效（keyi+1 < right），把右区间[keyi+1, right]压栈
如果左子区间有效（left < keyi‑1），把左区间[left, keyi‑1]压栈

判断条件：区间至少要有 2 个元素才需要入栈排序，只有 1 个元素不用处理。注意：先压右区间，后压左区间。栈后进先出，弹出的时候先处理左区间，和递归执行顺序保持一致。

代码如下：

// 快速排序非递归（栈模拟系统递归栈）
void QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	StackInit(&st);
	StackPush(&st, end);    //先压右边界
	StackPush(&st, begin);  //后压左边界
 
	while (!StackEmpty(&st)) // 栈不为空，还有区间待处理
	{
        // 取栈顶left，并Pop
		int left = StackTop(&st);
		StackPop(&st);
 
        // 再取栈顶right，并Pop
		int right = StackTop(&st);
		StackPop(&st);

		//调用前后指针法完成[left,right]区间单趟划分，得到基准下标keyi
		int keyi = PartSort3(a, left, right); 
		//划分后区间：[left, keyi‑1]   keyi(已就位)   [keyi+1, right]
 
		//右子区间：keyi+1 ~ right，区间元素≥2才压栈，不用处理单元素
		if (keyi + 1 < right) 
		{
			StackPush(&st, right);
			StackPush(&st, keyi + 1);
		}
 
		//左子区间：left ~ keyi‑1，元素≥2才压栈
		if (left < keyi - 1) 
		{
			StackPush(&st, keyi - 1); //先压右区间边界
			StackPush(&st, left);     //后压左区间边界
		}
	}
	StackDestroy(&st); //销毁栈，释放堆内存，防止内存泄漏
}

需要入栈的是数组的下标区间，且先入右再入左，因为栈是先进后出，循环条件是栈不为空。依次把需要进行单趟排的区间入栈，依次取栈里的区间出来做单趟划分，再把需要处理的子区间入栈。

逻辑等价二叉树的前序遍历；如果改用队列存储区间，则为层序遍历（广度优先）。

快速排序的特性总结：

时间复杂度：平均 O(N*log N)；最坏（完全有序）退化到 O(N^2)，通过三数取中优化可以避免最坏情况。
空间复杂度：O(log N)，来自递归 / 栈的深度；最坏可到 O(N)。
稳定性：不稳定排序，相等元素相对位置会发生改变。
综合性能：快速排序整体的综合性能和使用场景都是比较好的，所以才叫快速排序。

4.归并排序（MergeSort）

归并排序算法思想：

归并排序（MERGE-SORT）是建⽴在归并操作上的⼀种有效的排序算法,该算法是采⽤分治法（Divideand Conquer）的⼀个非常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个⼦序列有序，再使⼦序列段间有序。若将两个有序表合并成⼀个有序表，称为⼆路归并。归并排序核心步骤：

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//打印数组：遍历输出数组元素
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

//递归归并子函数，分治+合并
//a原数组，begin、end当前区间下标，tmp临时辅助数组
void _MergeSort(int* a, int begin, int end, int* tmp)
{
	//递归出口：区间只有1个元素/空，天然有序
	if (begin >= end)
	{
		return;
	}
	//计算中间位置，begin+(end‑begin)/2避免整型溢出
	int mid = begin + (end - begin) / 2;

	//递归拆分，把左右子区间分别变有序
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);

	//双指针归并两个有序区间 [begin1,end1] 和 [begin2,end2]
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin1;

	//两个区间都没遍历完，取较小值放入tmp
	while (begin1 <= end1 && begin2 <= end2)
	{
		//<=保证排序稳定，相等优先取左边
		if (a[begin1] <= a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	//拷贝左区间剩余元素
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	//拷贝右区间剩余元素
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	//把临时数组中归并好的数据拷贝回原数组
	memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

//归并排序对外接口
void MergeSort(int* a, int n)
{
	//开辟和原数组同样大小的临时数组，归并需要额外空间
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL) //内存开辟失败判断
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//调用递归子函数，排序[0,n‑1]
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp); //释放临时数组，防止内存泄漏
}

//测试函数
void TestMergeSort()
{
	int a[] = { 10, 6, 7, 1, 3, 9, 4, 2, 5 };
	//传入数组、元素个数，执行归并排序
	MergeSort(a, sizeof(a) / sizeof(int));
	//MergeSortNonR(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int)); //打印排序后数组
}

int main()
{
	TestMergeSort();
	return 0;
}

a. 归并排序是稳定的排序算法吗？

合并时如果左右区间出现相等元素，优先取左区间元素存入 tmp，相等元素相对顺序不变，所以归并排序是稳定排序。

b. 归并排序的时间复杂度是多少？

归并排序不受原数组有序程度影响，最好、最坏、平均情况时间复杂度都是 O(nlog n)。

c. 归并排序的空间复杂度是多少？

归并排序不是原地排序，合并需要额外临时数组。递归空间不会累加，同一时刻只使用一份临时空间，最大为 n，空间复杂度 O(n)。

归并排序的特性总结：（后序遍历）

缺点：需要O(N)额外空间；适合磁盘外排序。
时间复杂度：O(N*log N) 空间复杂度：O(N)
稳定性：稳定

归并排序非递归

递归靠函数栈先拆分再合并，代码简单但有栈溢出风险；非递归用循环迭代直接合并，无栈溢出但边界控制复杂，二者时间空间复杂度一致。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//打印数组
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

//归并排序 非递归版本
void MergeSortNonR(int* a, int n)
{
	//开辟临时辅助数组
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	int gap = 1;	//gap：每组有序段的长度，初始每组1个元素
	while (gap < n)
	{
		//每轮归并两组gap长度的有序区间，i向后跳2*gap
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;

			//第一段越界 或 第二段不存在，跳过本组
			if (end1 >= n || begin2 >= n)
			{
				continue;
			}
			//第二段末尾越界，修正边界
			if (end2 >= n)
			{
				end2 = n - 1;
			}

			int j = begin1;
			//双指针归并，<=保证排序稳定
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
			//拷贝剩余元素
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
			//把归并好片段复制回原数组
			int copyLen = end2 - i + 1;
			memcpy(a + i, tmp + i, sizeof(int) * copyLen);
		}
		gap *= 2;	//有序段长度翻倍
	}
	free(tmp);	//释放临时空间
}

void TestMergeSort()
{
	int a[] = { 10, 6, 7, 1, 3, 9, 4, 2, 5 };
	MergeSortNonR(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main()
{
	TestMergeSort();
	return 0;
}

5.非比较排序

（1）思想

计数排序又叫鸽巢排序，是哈希直接定址法的变形，适合整数、数据范围不大的场景，不做元素比较，依靠统计数值出现频次完成排序。

（2）操作步骤

先找到数组的最大值、最小值，确定计数数组的大小；
统计原数组中每个整数出现的次数，存入计数数组；
根据计数数组的频次，依次把数值写回原数组，完成排序。

图示如下：

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//打印数组
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

// 计数排序
void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	// 找出数组最大、最小值，确定数值区间
	for (int i = 1; i < n; ++i)
	{
		if (a[i] < min)
		{
			min = a[i];
		}
		if (a[i] > max)
		{
			max = a[i];
		}
	}

	// 计算计数数组大小
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	if (count == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	memset(count, 0, sizeof(int) * range); //计数数组全部置0

	//统计每个元素出现次数，a[i]-min做偏移，处理负数
	for (int i = 0; i < n; ++i)
	{
		count[a[i] - min]++;
	}

	// 根据统计次数回写到原数组
	int j = 0;
	for (int i = 0; i < range; ++i)
	{
		//count[i]是几，就写几遍 i+min
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
	free(count); //释放堆空间
}

void TestCountSort()
{
	int a[] = { 7, 3, 2, 7, 0, 3, -2, 9, -2, 5, 7, 0 };
	CountSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

int main()
{
	TestCountSort();
	return 0;
}

如果直接按照数值大小开辟0~5000的计数数组，但实际没有小于 1000 的数据，大量空间闲置浪费，这种是绝对映射，下标和真实数值完全对等。

针对该问题，使用a[i]‑min做偏移，以最小值作为计数数组下标起点，只开辟0~4000大小的计数数组，该方法称为相对映射，以此压缩空间，避免无效内存占用。

注意：

计数排序仅适合数据范围集中的场景；若数值范围range远大于待排序元素个数n，会产生巨大空间开销，不适合使用计数排序。
原始思路只支持非负整数；遇到负数时，依靠相对映射a[i]-min，把全部数据转化为非负下标，完成排序。

计数排序的特性总结： 计数排序属于非比较排序，数据范围集中时执行效率很高，但适用场景有限。

时间复杂度：O(max(N,range))

空间复杂度：O(range)

稳定性：稳定

补充：

range = max − min + 1，代表计数数组的长度；
稳定原因：回写时按下标从小到大依次放回，相等元素会保留原本先后次序。

三.排序算法复杂度及稳定性分析

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，⽽在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

乐奇 Rokid 开放社区

更多推荐

让界面替我“摇“一次：一个AR祈愿智能体的AIUI实践

乐奇 Rokid 开放社区

AR 智能眼镜并不是简单地在眼前放一块屏幕，而是把**摄像头、传感器、计算机视觉、空间定位、语音交互和云端服务**连接起来

乐奇 Rokid 开放社区

智能眼镜市场全景解析：从技术演进到产业格局

本文系统梳理智能眼镜市场，涵盖产品形态、技术演进、市场规模、产业链结构及竞争格局。指出智能眼镜正从音频交互向AR显示与空间计算演进，受AI大模型、供应链成熟与生态延伸驱动，呈现分层发展态势。虽面临场景刚需不足、续航重量矛盾与隐私挑战，但B端应用先行、AI原生设计与标准完善将推动行业迈向规模化渗透，未来需关注核心技术突破与真实使用数据。