同一组数,插入排序、选择排序、归并排序都能排对,差别在代价、边界和相等元素的相对次序。排序算法要同时看四笔账:平均时间、最坏时间、额外空间、稳定性。比较类算法靠关键字比较来决定次序,计数排序跳出这个框架,直接按值记账。

排序算法的四类分法

排序(sorting)是把一串记录按某个或某些关键字的大小递增或递减排列。购物筛选、院校排名、订单金额排序都是它的应用。常见比较类算法按思想分成四类:

排序算法按“插入、选择、交换、归并”四类分开:插入类有直接插入和希尔,选择类有直接选择和堆排序,交换类有冒泡和快排,归并单独一类;计数排序不属于这四类,它不做关键字比较

稳定性(stability)的定义是:待排序序列中有多个关键字相同的记录,排序后这些记录的相对次序保持不变,就说这个算法稳定;否则不稳定。稳定性不是排序函数的装饰属性,它取决于比较键和交换方式。同一个关键字不唯一时,输出本来就有多个合法答案;要不要保序,得先问清楚。

直接插入(insertion sort):有序前缀向右扩一格

直接插入排序维护一个不变式:[0, i] 这一段已经有序,把 a[i + 1] 插进去。

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

while 里的 > 而不是 >=,保证相等元素不会越过彼此,这是插入排序稳定的原因。比较次数和移动次数随逆序对数量变化:已经有序时一次都不搬,完全逆序时搬 n(n-1)/2 次。所以“数据越接近有序,它越快”不是经验,是可以数出来的。最好 O(n),平均和最坏 O(n²),空间 O(1)。

希尔:用 gap 先消掉远处的逆序对

希尔排序(Shell sort)又叫缩小增量排序。它把相隔 gap 的元素分到同一组,对每组做插入排序;然后缩小 gap,最后 gap == 1 时退化成普通插入排序。

void ShellSort(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        gap = gap / 3 + 1;
 
        for (int i = 0; i < n - gap; ++i)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0 && a[end] > tmp)
            {
                a[end + gap] = a[end];
                end -= gap;
            }
            a[end + gap] = tmp;
        }
    }
}

gap > 1 的每一轮都是预排序,目的不是让数组完全有序,而是让小元素一次跨过大段距离、把远处的逆序对成批消掉;收尾那轮 gap == 1,数组已经比较整齐,插入排序的代价很小。

希尔排序的三趟:初始 9 1 2 5 7 4 8 6 3 5,gap=5 时把相隔 5 的元素分到一组先排,gap=2 再排,gap=1 做最后一次直接插入;每趟结束数组都比上一趟更接近有序

希尔排序的复杂度没有单一答案,取决于增量序列。课件引用的严蔚敏教材给了一个具体结论:增量序列取 2^(t-k+1) - 1 时,时间复杂度可证到 O(n^(3/2));实验数据在某个 n 范围内约为 n^1.3,n 趋于无穷时可减少到 n(log₂n)²。

严蔚敏《数据结构(C 语言版)》对希尔排序复杂度的说明:增量序列取 2^(t-k+1)-1 时可证到 O(n^(3/2)),实验数据在某个 n 范围内约为 n^1.3;增量序列没有唯一最优解,所以希尔排序只能给区间,不给单一阶

通行说法是:平均约 O(n^1.3),最好 O(n log n),最坏 O(n²),辅助空间 O(1),不稳定。最好情况不是 O(n):即使输入已经有序,gap 递减仍要走完 log n 趟,每趟都要扫一遍数组。课件表格里希尔一行同时放了 ~O(nlog n)、O(n²)、O(n^1.3)、O(n²) 四个复杂度值,却只有平均、最好、最坏三列,列对齐出了问题;按增量序列不同取对应值,才是这张表想表达的意思。

课件说“希尔排序的效率肯定高于直接插入排序”,这个说法偏满。平均意义上它更快,但不保证每一个输入都更快:小数组、已经接近有序的数组,多趟预排序可能反而更贵。希尔排序不稳定,因为相等元素会被分到不同组,跨组移动时相对次序就乱了。反例是 5a 8 2 5b 9:gap = 2 时第一组 5a 2 9 排成 2 5a 9,第二组 8 5b 排成 5b 8,数组变成 2 5b 5a 8 9,5b 跑到了 5a 前面。

直接选择(selection sort):一趟同时定最小和最大

直接选择排序每一趟从待排序区间里选出最小和最大的元素,分别放到区间两端,然后缩小区间。

static void Swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}
 
void SelectSort(int* a, int n)
{
    int begin = 0, end = n - 1;
    while (begin < end)
    {
        int mini = begin, maxi = begin;
 
        for (int i = begin; i <= end; ++i)
        {
            if (a[i] > a[maxi])
                maxi = i;
            if (a[i] < a[mini])
                mini = i;
        }
 
        if (begin == maxi)
            maxi = mini;      /* 第一次交换会把最大值挪到 mini 的位置 */
 
        Swap(&a[mini], &a[begin]);
        Swap(&a[maxi], &a[end]);
        ++begin;
        --end;
    }
}

if (begin == maxi) maxi = mini; 这一行救的是“最大值恰好站在 begin”的情况。第一次交换把最小值换到 begin,最大值被挤到 mini 的位置,但 maxi 还记着旧的 begin;不修正的话,第二次交换拿 a[maxi] 去和末尾换,换走的是最小值,最大值反而留在了开头。这个分支只在特定输入下出现,随机数据未必撞得上。

选择排序的时间复杂度在最好、平均、最坏都是 O(n²):不管数据什么样,每一趟都要把区间扫一遍。空间 O(1)。它不稳定,反例是 5a 8 5b 2 9:第一轮最小值 2 和第一个 5a 交换,5a 被扔到后面,跑到了 5b 的右边,结果是 2 8 5b 5a 9。

冒泡(bubble sort):exchange 必须每趟清零

void BubbleSort(int* a, int n)
{
    for (int i = 0; i < n; ++i)
    {
        int exchange = 0;               /* 每轮都要重新置零 */
        for (int j = 0; j < n - i - 1; ++j)
        {
            if (a[j] > a[j + 1])
            {
                Swap(&a[j], &a[j + 1]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;                      /* 这一轮没换过,已经有序 */
    }
}

课件把 int exchange = 0; 写在了外层循环外面。后果不是“优化效果差一点”,而是优化彻底失效:只要第一轮发生过一次交换,exchange 就永远是 1,break 再也不会触发,后面的轮次照跑不误。只有“一开始就完全有序”的数组才能提前退出,那恰好是最不需要优化的情况。变量挪进循环体,它才有意义。

冒泡最好 O(n)(一轮扫完无交换),最坏与平均 O(n²),空间 O(1)。它稳定,因为只在严格大于时交换,相等元素不会被换到彼此后面。

快速排序(quicksort):三种划分与两个优化

快排的框架是三行:取基准、划分、递归两边。真正容易写错的是划分。课件给了霍尔(Hoare)、挖坑、前后指针(Lomuto)三种,思路不同,边界条件都一样刁。

霍尔划分:右指针先走

static int GetMidIndex(int* a, int left, int right)
{
    int mid = left + (right - left) / 2;   /* 避免 left + right 溢出 */
 
    if (a[left] > a[mid])
    {
        if (a[mid] > a[right])
            return mid;
        else if (a[left] > a[right])
            return right;
        else
            return left;
    }
    else
    {
        if (a[left] > a[right])
            return left;
        else if (a[mid] > a[right])
            return right;
        else
            return mid;
    }
}
 
int PartHoare(int* a, int left, int right)
{
    int midi = GetMidIndex(a, left, right);
    Swap(&a[left], &a[midi]);
 
    int keyi = left;
    int key = a[keyi];
    ++left;
 
    while (left <= right)
    {
        while (left <= right && a[right] > key)
            --right;
        while (left <= right && a[left] < key)
            ++left;
 
        if (left <= right)
        {
            Swap(&a[left], &a[right]);
            ++left;
            --right;
        }
    }
 
    Swap(&a[keyi], &a[right]);
    return right;
}

基准在左边时,必须让右指针先走。因为要和基准交换的是 right 停下的位置,这个位置上的值必须不大于基准,交换后基准才能落到正确的一侧。如果让左指针先走,它可能停在一个大于基准的值上,交换后基准左边混进一个大元素,整段划分作废。

a[right] > key 和 a[left] < key 都故意不把“等于”算进去。遇到相等就停下来交换,相等的值会被摊到基准两边;如果写成 >= 或 <= 跳过相等,大量重复数据会让指针卡在相等元素上,划分退化成一边倒。

霍尔划分里,右指针停下、左指针追上来时,相遇位置的值可能大于 key、等于 key 或小于 key(三幅图的数组分别是 6 1 2 7 9 3、6 1 2 7 6 3、6 1 2 7 4 3);所以内层循环必须把等于 key 的情况也停下来交换,否则相等的元素会全被推到一边

课件这段代码的第二个内层循环注释写成了“右边找小”,实际做的是“左边找大”。注释反了不会让程序出错,但会让人把职责记反,然后顺手把条件写成 <=,相等元素被跳过,划分再次失效。课件主框架的注释还写着“划分 [left,right)”,代码和递归用的却是闭区间 [left,right];这里按闭区间写。

挖坑法:基准取走,留一个洞

int PartHole(int* a, int left, int right)
{
    int key = a[left];
    int hole = left;
 
    while (left < right)
    {
        while (left < right && a[right] >= key)
            --right;
        a[hole] = a[right];
        hole = right;
 
        while (left < right && a[left] <= key)
            ++left;
        a[hole] = a[left];
        hole = left;
    }
 
    a[hole] = key;
    return hole;
}

挖坑法把基准先“取出来”,数组头留下一个坑。右指针找到比基准小的数,填进左坑,当前位置变成新坑;左指针找到比基准大的数,填进右坑,当前位置再变成新坑。两个指针相遇时,剩下的坑就是基准的位置。课件代码里有一行 int mid = a[left];,声明之后从没使用,真正的基准是下一行的 key,这行是改代码时的残留,删掉。

挖坑法先把第一个元素 6 存进 key,数组头就空出一个坑;L 从左边、R 从右边出发,R 先往左找比 key 小的数,找到后填进这个坑,坑的位置随之移到 R 停下的地方

前后指针法:让 prev 守住小元素区

int PartLomuto(int* a, int left, int right)
{
    int keyi = left;
    int prev = left;
 
    for (int cur = left + 1; cur <= right; ++cur)
    {
        if (a[cur] < a[keyi] && ++prev != cur)
            Swap(&a[cur], &a[prev]);
    }
 
    Swap(&a[keyi], &a[prev]);
    return prev;
}

prev 始终停在“已确认的小元素区”末尾,cur 从左往右扫。++prev != cur 用短路避免自己和自己交换。它在全相等数据上会退化:条件 a[cur] < a[keyi] 一个都不成立,基准每次落在最左端,递归深度变成 n,时间复杂度回到 O(n²)。霍尔版本因为相等也交换,反而能把相等元素摊到两边。

相等元素在霍尔划分里会被反复交换:这组 6 6 6 8 6 6 经过四次交换后,right 停在第一个 6 的位置,left 已经越过它,最后从 right 处分成两段;如果遇到相等就跳过,指针会卡在相等元素上,划分退化成一边倒

三数取中与小区间插入

三数取中从 left、mid、right 三个位置里选出值居中的那个,换到 left 当基准。它能避开“已经有序”“完全逆序”这两种最常见的退化输入,但不能消灭最坏情况:专门构造的数据仍能让快排退到 O(n²)。快排的平均和最好时间是 O(n log n),最坏 O(n²),递归栈平均 O(log n)、最坏 O(n)。课件只写了 O(nlogn) 和 O(logn),没提最坏情况,面试里通常会被追问。

小区间优化是另一笔账:递归到长度很小的区间时,快排的递归调用和划分开销已经超过插入排序。常见做法是长度小于等于 10 时直接调用 InsertSort,不再继续划分。

void QuickSort(int* a, int left, int right)
{
    if (left >= right)
        return;
 
    if (right - left + 1 <= 10)
    {
        InsertSort(a + left, right - left + 1);
        return;
    }
 
    int meet = PartHoare(a, left, right);
    QuickSort(a, left, meet - 1);
    QuickSort(a, meet + 1, right);
}

非递归版本

非递归快排用一个显式栈保存待划分的区间。区间用结构体表示,栈的容量按最坏情况开 n + 2 个,避免递归深度退化时溢出。

typedef struct
{
    int left;
    int right;
} Range;
 
void QuickSortNonR(int* a, int left, int right)
{
    if (left >= right)
        return;
 
    int cap = right - left + 2;
    Range* st = (Range*)malloc(sizeof(Range) * (size_t)cap);
    if (st == NULL)
        return;
 
    int top = 0;
    st[top++] = (Range){left, right};
 
    while (top > 0)
    {
        Range r = st[--top];
        if (r.left >= r.right)
            continue;
 
        int meet = PartHoare(a, r.left, r.right);
        if (r.left < meet - 1)
            st[top++] = (Range){r.left, meet - 1};
        if (meet + 1 < r.right)
            st[top++] = (Range){meet + 1, r.right};
    }
 
    free(st);
}

先压左区间还是先压右区间不影响正确性,只影响处理顺序;每个区间出栈时独立划分,和递归版本等价。栈的深度最坏是 O(n),空间和递归版的最坏情况一样。

归并(merge sort):先切到单元素,再两两合并

归并排序(Merge sort)是分治的典型应用:把序列对半切开,分别排好,再把两个有序段合并成一个有序段。合并时相等就取左段,左段元素本来就在前面,所以归并稳定。

void _MergeSort(int* a, int left, int right, int* tmp)
{
    if (left >= right)
        return;
 
    int mid = left + (right - left) / 2;   /* 不用 (left + right) / 2 */
    _MergeSort(a, left, mid, tmp);
    _MergeSort(a, mid + 1, right, tmp);
 
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right)
    {
        if (a[i] <= a[j])
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    }
 
    while (i <= mid)
        tmp[k++] = a[i++];
    while (j <= right)
        tmp[k++] = a[j++];
 
    for (int t = left; t <= right; ++t)
        a[t] = tmp[t];
}
 
void MergeSort(int* a, int n)
{
    if (n <= 1)
        return;
 
    int* tmp = (int*)malloc(sizeof(int) * (size_t)n);
    if (tmp == NULL)
        return;
 
    _MergeSort(a, 0, n - 1, tmp);
    free(tmp);
}

课件 _MergeSort 里写的是 int mid = (right + left) / 2;。left + right 在元素个数接近 INT_MAX 时会溢出成负数,mid 随之错位,递归切分出非法区间。改成 left + (right - left) / 2 就不会溢出。

课件合并时写的是 if (a[begin1] < a[begin2]),相等时取右段,右段元素先出,左段原本靠前的相等元素被排到后面,归并排序立刻不稳定。把 < 改成 <=,相等取左段,稳定性才回来。稳定性就藏在这一个符号里。

课件 MergeSort 里用的是 new int[n] 和 delete[] tmp,这是 C++ 语法,放进 .c 文件编译不过。C 版本用 malloc 加 free,并检查返回值。

非递归归并从长度 1 开始,两两合并,再把段长翻倍:

void MergeSortNonR(int* a, int n)
{
    if (n <= 1)
        return;
 
    int* tmp = (int*)malloc(sizeof(int) * (size_t)n);
    if (tmp == NULL)
        return;
 
    for (int gap = 1; gap < n; gap *= 2)
    {
        for (int i = 0; i < n; i += 2 * gap)
        {
            int left1 = i;
            int right1 = i + gap - 1;
            int left2 = i + gap;
            int right2 = i + 2 * gap - 1;
 
            if (right1 >= n)
                right1 = n - 1;
            if (left2 >= n)
                left2 = n;
            if (right2 >= n)
                right2 = n - 1;
 
            int k = i;
            int p1 = left1;
            int p2 = left2;
 
            while (p1 <= right1 && p2 <= right2)
            {
                if (a[p1] <= a[p2])
                    tmp[k++] = a[p1++];
                else
                    tmp[k++] = a[p2++];
            }
 
            while (p1 <= right1)
                tmp[k++] = a[p1++];
            while (p2 <= right2)
                tmp[k++] = a[p2++];
 
            for (int t = i; t < k; ++t)
                a[t] = tmp[t];
        }
    }
 
    free(tmp);
}

边界处理是这一段最容易错的地方:右段可能根本不存在,left2 >= n 时把 left2 设成 n、right2 设成 n - 1,后面的 while 自然不执行;右段可能被截断,right2 要夹到 n - 1。归并的时间恒为 O(n log n),最好、平均、最坏都一样;空间 O(n),那块 tmp 必须提前申请。

计数排序(counting sort):不开比较,直接按值记账

计数排序(Counting sort)不做关键字比较,先统计每个值出现了多少次,再按值从小到大把记录写回原数组。它是哈希直接定址法的变形应用。

void CountSort(int* a, int n)
{
    if (n <= 0)
        return;
 
    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*)calloc((size_t)range, sizeof(int));
    if (count == NULL)
        return;
 
    for (int i = 0; i < n; ++i)
        ++count[a[i] - min];
 
    int j = 0;
    for (int v = 0; v < range; ++v)
    {
        while (count[v] > 0)
        {
            a[j++] = v + min;
            --count[v];
        }
    }
 
    free(count);
}

range = max - min + 1,最小值自己也要占一个下标;只写 max - min 会少一格,最大值映射到 range 就越界。时间 O(n + range),空间 O(range),只适合范围集中的整数;范围一大,空间先炸。按值回填的版本对纯整数稳定;如果记录还带其他字段,要保留相同关键字的相对次序,得先做前缀和,再从右往左放置,才是完整的稳定计数排序。

稳定性与复杂度总表

算法平均最好最坏辅助空间稳定性
直接插入O(n²)O(n)O(n²)O(1)稳定
希尔约 O(n^1.3)O(n log n)O(n²)O(1)不稳定
直接选择O(n²)O(n²)O(n²)O(1)不稳定
冒泡O(n²)O(n)O(n²)O(1)稳定
堆排序(heap sort)O(n log n)O(n log n)O(n log n)O(1)不稳定
快速排序O(n log n)O(n log n)O(n²)平均 O(log n),最坏 O(n)不稳定
归并排序O(n log n)O(n log n)O(n log n)O(n)稳定
计数排序O(n + range)O(n + range)O(n + range)O(range)稳定

稳定性可以用小例子逐个验证:

  • 直接选择:5a 8 5b 2 9,第一轮 2 和 5a 交换,得到 2 8 5b 5a 9,两个 5 反了。
  • 希尔:5a 8 2 5b 9,gap = 2 时 5a 和 5b 被分到不同组,跨组移动后 5b 跑到 5a 前面。
  • 堆排序:2a 2b 1,建大堆后堆顶换到末尾,再下沉,最后得到 1 2b 2a。课件用一个全相同的 2 2 2 2 作为反例,这组数据标不出谁前谁后,换成带标记的 2a 2b 才看得出不稳定。
  • 快速排序:5 3a 3b 4 3c 8 9 10 11,划分时相等键被换到基准两边,原来的先后次序不保证。
  • 归并:合并时 <= 取左段,相等元素保持左段在前;改成 < 立刻不稳定。
  • 插入、冒泡:只在严格大于时移动或交换,相等元素不越过彼此,稳定。
  • 计数:按值回填的纯整数版本稳定;带卫星数据时要用前缀和从右往左放。

选排序算法跟选数据结构一样,先问清楚“要不要稳定、数据范围多大、内存够不够”,再谈速度。需要稳定又不想自己写,std::stable_sort 在额外内存够用时是 O(n log n);std::sort 更快,但不承诺稳定。比较类算法的下界是 O(n log n),计数排序能突破它,是因为它没有走比较这条路,代价是把值域当成数组下标。