第07章 排序：七大排序算法全解析

这一篇在干嘛？

排序是算法界的”试金石”：同一个问题装下了几乎所有设计思想——增量改进（希尔）、堆的应用（堆排序）、分治（归并/快排）、下界证明（决策树）、按位分发（桶/基数）。本章逐一拆解，并回答那个面试高频题：这么多 $O(N\log N)$ 排序到底该用哪个？

7.1 预备与约定

约定：$N$ 个元素，比较排序基于 < 比较。稳定性（相等元素排序后保持原相对顺序）在某些场景是硬需求（多关键字排序的第二遍就依赖它）。原书用 Comparable 模板实现，默认升序。

7.2 插入排序：小数据之王

思想：像理牌——第 $p$ 趟把 $a[p]$ 插入前面已排好的 $a[\mathrm{0..}p-1]$ 中合适的位置：

template <typename Comparable>
void insertionSort(vector<Comparable> &a) {
    for (int p = 1; p < a.size(); ++p) {
        Comparable tmp = std::move(a[p]);       // 抽出待插牌
        int j;
        for (j = p; j > 0 && tmp < a[j - 1]; --j)
            a[j] = std::move(a[j - 1]);         // 大的逐个后移
        a[j] = std::move(tmp);                  // 落座
    }
}

分析：第 $p$ 趟最多比较 $p$ 次，总计 $O(N^2)$；逆序数（inversion）恰好等于移动总次数——所以插入排序实际耗时 $O(I+N)$，$I$ 是逆序数。几乎有序的数组它是线性的（每个元素移动不到几次），这是它留在快排实现里处理小数组的原因。

下界（定理 7.2）：交换相邻元素的排序，平均每次交换消 1 个逆序，平均逆序数 $N(N-1)/4$，所以这类”相邻交换”算法平均 $O(N^2)$——想超越二次方，必须做长距离交换。

7.3 希尔排序：长距离跳跃

思想：按增量序列分组做插入排序，增量逐步缩小到 1。远距离的”粗排”先行，为最后一趟普通插入扫清大部分逆序：

void shellsort(vector<Comparable> &a) {
    for (int gap = a.size() / 2; gap > 0; gap /= 2)     // Shell 原始增量：折半
        for (int i = gap; i < a.size(); ++i) {
            Comparable tmp = std::move(a[i]);
            int j = i;
            for (; j >= gap && tmp < a[j - gap]; j -= gap)
                a[j] = std::move(a[j - gap]);           // 与 gap 距离前的元素比较
            a[j] = std::move(tmp);
        }
}

复杂度取决于增量序列：

• Shell 原始增量（N/2, N/4, …, 1）：最坏 $O(N^2)$——增量互为倍数，前面的工作会被后面抵消。
• Hibbard 增量（1, 3, 7, …, $2^k-1$）：最坏 $O(N^{3/2})$。
• 实践中推荐的序列（如 Sedgewick 1,5,19,41,…）可达 $O(N^{4/3})$，且代码短、无递归、常数小，中等规模很好用。

白话：先用大步子把”离谱地远”的元素送到大致正确的位置，最后一步的小步插入就几乎不用动了。它是”插入排序的加速器”，没有递归没有辅助数组，是嵌入式场景的宠儿。

7.4 堆排序：buildHeap 的免费红利

思想：buildHeap $O(N)$ 建大根堆；然后 N−1 次 deleteMax，每次把最大元换到数组末尾（与堆尾交换后 percolateDown(1, 堆缩小)）：

分析：N 次 deleteMax 每次 $O(\log N)$，总计 $O(N\log N)$ 最坏情形——且原地、无辅助数组。缺点：缓存局部性差（下滤跳跃访问）、不稳定，实测通常输给精心实现的快排。

白话：把数组建成”最大元浮顶”的堆，然后反复”摘顶放尾”——堆每次缩小一格，数组尾部从后往前长出有序区。

7.5 归并排序：分治的教科书

思想：递归排序两半，再线性合并两个有序表：

void mergesort(vector<Comparable> &a, vector<Comparable> &tmpArray,
               int left, int right) {
    if (left < right) {
        int center = (left + right) / 2;
        mergesort(a, tmpArray, left, center);
        mergesort(a, tmpArray, center + 1, right);
        merge(a, tmpArray, left, center + 1, right);   // 合并两个有序段
    }
}
 
void merge(vector<Comparable> &a, vector<Comparable> &tmpArray,
           int leftPos, int rightPos, int rightEnd) {
    int leftEnd = rightPos - 1, tmpPos = leftPos;
    int numElements = rightEnd - leftPos + 1;
    while (leftPos <= leftEnd && rightPos <= rightEnd)   // 两头比小，小的先走
        if (a[leftPos] <= a[rightPos])                   // <= 保证稳定
            tmpArray[tmpPos++] = std::move(a[leftPos++]);
        else
            tmpArray[tmpPos++] = std::move(a[rightPos++]);
    while (leftPos <= leftEnd)   // 左段剩余
        tmpArray[tmpPos++] = std::move(a[leftPos++]);
    while (rightPos <= rightEnd) // 右段剩余
        tmpArray[tmpPos++] = std::move(a[rightPos++]);
    for (int i = 0; i < numElements; ++i, --rightEnd)
        a[rightEnd] = std::move(tmpArray[rightEnd]);
}

分析：$T(N)=2T(N/2)+O(N)$ ⇒ $O(N\log N)$ 最坏保证，且稳定。代价：需要 $O(N)$ 辅助数组（本实现把拷回的往返也省了：交替使用输入/输出数组），常数比快排大。外部排序的基石（数据放磁盘上无法随机访问时，靠多路归并）。

白话：分到只剩单元素（天然有序），再两两合并、四四合并……像锦标赛决赛圈逐步汇合。合并时”两边队首比小”一行搞定。

7.6 快速排序：实践冠军

思想：选枢纽元（pivot），把数组划分成”小于 | 枢纽 | 大于”三段，两段递归——与归并相反，工作量在”分”上，“合”是免费的。

枢纽元选择：

• 取 a[low]（错误做法：有序输入退化 $O(N^2)$）。
• 随机取（好，但随机数生成不便宜）。
• 三数中值（first, center, last 的中位数）：实践标配，几乎不会退化。

划分策略：指针 i 从左找 ≥ pivot 的、j 从右找 ≤ pivot 的，交换；相遇后 pivot 归位。把等于 pivot 的元素两边都停（避免极端输入全等时退化）——这是实践中最重要的小细节。

小数组切换插入排序：递归到长度 ≈ 10 以下改用插入排序，实测提速 10–20%（消除递归开销与小数组的划分浪费）。

分析：

• 最坏 $O(N^2)$（枢纽每次都是极值，如有序数组选首元素）。
• 最好/平均 $O(N\log N)$：平均递推 $T(N)\approx 2T(N/2)\cdot \frac{1}{2}\cdot$…（每次划分期望均衡），解得 $1.38N\log N$ 次比较。
• 不稳定。实践中因内层循环极简、缓存友好，几乎总是最快的通用排序——C 的 qsort、C++ sort 都以它为基础。

线性期望时间的选择：quickselect

只要”第 k 小”不要全排序：划分后只有一侧需要递归（另一侧直接丢弃）。平均 $O(N)$——对比排序后取第 k 个的 $O(N\log N)$，这是快排划分思想的一次”半价变现”。

7.7 通用下界：为什么 O(N log N) 是比较排序的天花板

决策树：任何比较排序的每个”分支判断”是二叉分叉，N 个元素有 $N!$ 种排列，决策树必须有 $N!$ 个叶子，高至少 ${\log }_2(N!)=\Theta (N\log N)$（Stirling 公式）。

白话：每次比较只能获得 1 bit 信息，区分 $N!$ 种可能至少要 ${\log }_{2}N!\approx N\log N$ 次比较。绕开方式：不做比较——桶排序/基数排序直接”看值放位置”，突破到线性（前提：值域有限或可按位分发）。

7.8 线性排序：桶排序与基数排序

桶排序：值域 $[0,M]$ 且 $M$ 不大时，直接开 M 个桶散列，逐桶倒出——$O(N+M)$。

基数排序（radix sort）：多关键字按从最低位到最高位逐位做稳定排序（每位用桶/计数排序）。$d$ 位整数共 $d$ 趟，每趟 $O(N+b)$（b 为进制），总计 $O(d(N+b))$——与 $N$ 成线性！

白话：基数排序像快递分拣——先按电话尾号分堆（每堆内部已按尾号有序），再按倒数第二位把这些堆依序叠起来……最低位优先（LSD）+ 每一轮稳定，保证高位相同时低位顺序不被破坏。

适用前提：元素可按位分发且位数固定（整数、定长字符串）。所以通用库排序是快排家族，专用场景（海量整数）用基数。

7.9 选型速查表

算法	平均	最坏	稳定	额外空间	一句话
插入	$O(N^2)$	$O(N^2)$	✔	$O(1)$	近乎有序/小数组之王
希尔	视增量	视增量	✘	$O(1)$	中等规模的实用派
堆排	$O(N\log N)$	$O(N\log N)$	✘	$O(1)$	最坏保证 + 原地
归并	$O(N\log N)$	$O(N\log N)$	✔	$O(N)$	稳定 + 外部排序基石
快排	$O(N\log N)$	$O(N^2)$	✘	$O(\log N)$ 栈	实践最快
基数	$O(d(N+b))$	同左	✔	$O(N+b)$	定长键、超大 N

常见坑

① 快排枢纽选首元素：对已排序输入退化 $O(N^2)$——三数中值是底线。② 划分时”等于枢纽”处理错：全等数组若单边扫不停会退化，正确策略是两边都停并交换。③ 归并的 <= 写成 <：稳定性丢失，多关键字第二遍排序直接出错。④ 递归型 merge 的临时数组在递归里反复 new：应在入口分配一次传下去。

通关标准

学完本篇你应该能做到：① 手写插入排序、归并 merge、快排划分三段核心代码；② 用逆序数解释插入排序的实际耗时与简单排序的 Ω(N²) 下界；③ 复述希尔增量的选择如何影响复杂度；④ 画出三元素决策树并推导比较排序下界 Θ(N log N)；⑤ 面对场景（稳定性/最坏保证/近乎有序/海量整数）立刻选出正确算法。

为什么"只交换相邻元素"的排序平均必然 Ω(N²)？

每次相邻交换至多消除一个逆序，平均逆序数 N(N−1)/4 ≈ N²/4，故总交换次数下界就是 Ω(N²)（定理 7.2 的证明核心）。

希尔排序的 Shell 原始增量（N/2, N/4, …）为什么不好？

增量之间互为倍数：同一批”错位元素”会在多个增量阶段反复搬家，前面的粗排成果被后继阶段浪费；Hibbard 增量 2^k−1 保证相邻增量互质，最坏降到 O(N

堆排序是 O(N log N) 且原地，为什么实践中常输给快排？

下滤在父子下标间大跨度跳跃，缓存命中率低；比较次数常数也更大。快排内层顺序扫描、极简，缓存友好。最坏保证场景才轮到堆排（或 introsort 混合）。

quickselect 为什么平均是 O(N)？最坏呢？

每层只递归一侧：N + N/2 + N/4 + … ≈ 2N（期望均衡划分）。最坏 O(N²)（划分每次极不均衡）。

基数排序凭什么突破比较排序的 Ω(N log N) 下界？

下界只约束”基于比较”的算法。基数排序不比较，按位分发进桶——它利用了键的具体结构（位数固定、值域有限），信息是”查表”获得而非比较获得的。