Lecture 35：排序算法总结

This note is currently available in Chinese. The original wording, formulas and diagrams are preserved to avoid an unverified technical translation.

排序综合题不能只背一张表。先从“每趟做什么”辨认算法，再用时间、空间、稳定性、适用存储结构和输入特征逐项验证；所有复杂度结论都带有实现与输入前提。

35.1 内部排序算法总表

下表按常见统考实现给出紧确量级。$n$ 为记录数，$d$ 为关键字位数，$r$ 为每位可能取值数，$k$ 为计数排序的关键字取值范围大小。

算法	最好时间	平均时间	最坏时间	辅助空间	稳定性	核心特点
直接插入	$\Theta(n)$	$\Theta(n^2)$	$\Theta(n^2)$	$O(1)$	稳定	前缀有序，适合小规模或近乎有序
折半插入	$\Theta(n\log n)$	$\Theta(n^2)$	$\Theta(n^2)$	$O(1)$	稳定	只减少定位比较，不能消除批量移动
希尔	依增量序列而定	依增量序列而定	常见折半增量为 $O(n^2)$	$O(1)$	不稳定	对多个增量子表做插入排序
冒泡（带标志）	$\Theta(n)$	$\Theta(n^2)$	$\Theta(n^2)$	$O(1)$	稳定	相邻交换，可检测已有序后提前结束
快速	$\Theta(n\log n)$	$\Theta(n\log n)$	$\Theta(n^2)$	平均 $O(\log n)$，最坏 $O(n)$	不稳定	划分递归，枢轴质量决定性能
简单选择	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(n^2)$	$O(1)$	不稳定	比较次数固定，交换次数少
堆排序	$\Theta(n\log n)$	$\Theta(n\log n)$	$\Theta(n\log n)$	$O(1)$	不稳定	线性建堆，反复输出堆顶
二路归并	$\Theta(n\log n)$	$\Theta(n\log n)$	$\Theta(n\log n)$	$O(n)$	稳定	每层线性归并，时间不随初始有序度明显改善
LSD 基数	$\Theta(d(n+r))$	$\Theta(d(n+r))$	$\Theta(d(n+r))$	常见为 $O(r)$ 或 $O(n+r)$	稳定	非比较排序，依赖关键字可分解为 $d$ 位
计数排序	$\Theta(n+k)$	$\Theta(n+k)$	$\Theta(n+k)$	稳定实现为 $O(n+k)$	稳定实现可稳定	非比较排序，要求整数键的有限值域可承受

读表注意：

折半插入在每趟都做折半定位，因此最好情况下比较总量仍为 $\Theta(n\log n)$；平均和最坏情况下，$\Theta(n^2)$ 的记录移动占主导。
快排只有在划分较均衡时递归深度才为 $\Theta(\log n)$；连续产生规模为 $0$ 与 $n-1$ 的子问题时，时间和栈深分别退化为 $\Theta(n^2)$ 与 $\Theta(n)$。
希尔排序的时间复杂度必须结合增量序列说明，不能把某一增量序列的结论推广到所有实现。
基数排序若只保存各桶首尾指针并复用记录链域，附加队列信息可为 $O(r)$；若另开桶存储全部记录，则为 $O(n+r)$。
标准自底向上建堆是 $\Theta(n)$，但完整堆排序还要做 $n-1$ 次删除堆顶和调整，因此总时间仍为 $\Theta(n\log n)$。
计数排序的 $k$ 是最大键与最小键之差加 $1$；当 $k$ 远大于 $n$ 时，时间和空间都会浪费，不能只看它对 $n$ 的线性项。

35.1.1 比较排序的下界

对 $n$ 个互异关键字，基于比较的排序必须区分 $n!$ 种排列；二叉判定树高度至少为：

$$ \left\lceil\log_2(n!)\right\rceil=\Omega(n\log n) $$

因此任何比较排序的最坏比较次数都不可能优于 $\Omega(n\log n)$；在等概率排列等常见模型下，平均比较次数也有同阶下界。
基数排序不是比较排序，不受该判定树下界直接约束，但它受关键字结构、位数 $d$、基数 $r$ 和额外空间限制。

35.2 存储结构与稳定性

35.2.1 存储结构的适配

场景	更合适的算法	原因与边界
顺序表、要求原地	直接插入、希尔、冒泡、简单选择、堆	可直接按下标访问；堆与希尔尤其依赖高效随机定位
顺序表、追求平均速度	快速排序	连续区间划分方便，但要防止枢轴导致退化
链表、要求稳定且 $O(n\log n)$	归并排序	可通过改链合并，不要求随机访问；自底向上的链式实现可只用 $O(1)$ 个额外结点指针
链表、小规模或近乎有序	直接插入排序	找到位置后改链即可，移动记录代价小
固定位数的整数或字符串关键字	基数排序	链式桶分配与收集自然，但必须保持每趟稳定

折半查找虽然只需 $O(\log n)$ 次比较，但链表不能 $O(1)$ 访问中点，因此折半插入在链表上通常失去优势。
希尔排序与数组堆排序依赖下标间隔或父子下标关系，通常不用于普通链表。
“某算法能否改写到某存储结构”与“是否适合”不是一回事；快排、冒泡、选择等也能设计链式版本，但不一定保留顺序表实现的常数优势。

35.2.2 稳定性结论与成立条件

稳定：直接插入、折半插入、冒泡、归并、基数。
不稳定：希尔、快速、简单选择、堆。
稳定性是具体算法实现的性质，而不是排序结果的性质：
- 插入排序应把新记录放在已有相等记录之后；
- 冒泡排序只交换严格逆序的相邻记录；
- 归并时关键字相等应先取左段记录；
- 基数排序每一趟的分配与收集都必须稳定。
源 PDF 中“选择插入排序”不是规范算法名，此处按其实际内容更正为简单选择排序。

题型：#稳定性判断

给相等关键字加标签，例如 3a, 3b，并令 3a 原先在前。
按算法的真实交换、移动或收集规则走一遍。
若存在某个合法输入能使 3b 越过 3a，该算法即不稳定；只看比较条件是否含等号并不足够。
远距离交换或跨组移动是高风险信号，所以希尔、快速、简单选择和堆排序通常不稳定。

35.3 排序过程辨识

35.3.1 直接插入与折半插入

两者都维护有序前缀，并把当前记录插入其中；区别只在于如何寻找插入位置。
直接插入从后向前顺序比较；折半插入用二分查找位置，但定位后仍要整体后移后缀。
折半插入必须统一相等关键字的边界策略；插到已有相等记录之后时可保持稳定。

35.3.2 插入排序与简单选择排序

维度	直接插入排序	简单选择排序
已排序区	前缀有序，长度每趟加一	前缀已放好当前最小值
本趟扫描对象	向前扫描已排序区找插入位置	向后扫描未排序区找最小值
主要移动	多个较大元素整体后移	扫描结束后通常做一次交换
比较次数	随初始有序度变化	固定为 $n(n-1)/2$
稳定性	稳定	不稳定

“暂存未排序区首元素，再向前移动较大元素”是插入排序。
“扫描整个未排序区记住最小下标，最后与边界交换”是简单选择排序。
记录本身很大且交换代价高时，简单选择的交换次数至多 $n-1$，但它的比较次数仍为 $\Theta(n^2)$。

35.3.3 希尔与冒泡

希尔排序按增量 $h$ 把间隔为 $h$ 的元素看作同一子表，各子表分别做直接插入；最终必须取 $h=1$。

冒泡排序每趟扫描当前无序区，通过相邻交换把一个极值送到边界。带交换标志时，已有序输入只需一趟，时间为 $\Theta(n)$。

35.3.4 快速、堆与归并

快排每次划分使枢轴到达最终位置。图中的 $\log n$ 层只对应较均衡划分；极端不平衡时递归深度可达 $n$。

堆只保证父结点不小于（或不大于）孩子，并非全局有序。建堆为 $\Theta(n)$；每次交换堆顶后下坠为 $O(\log n)$，完整排序为 $\Theta(n\log n)$。

二路归并共有 $\Theta(\log n)$ 层，每层处理全部 $n$ 个元素，故总时间为 $\Theta(n\log n)$；数组实现通常需要 $O(n)$ 辅助空间。

35.3.5 一眼识别特征

现象	对应算法
相邻逆序即交换，某极值逐趟移动到边界	冒泡排序
选枢轴，左右指针划分，枢轴到最终位置	快速排序
下标满足 $i,2i,2i+1$ 或 $i,2i+1,2i+2$，不断上升或下坠	堆/堆排序
两个有序段用三个指针合为一个有序段	归并排序
按个位、十位等依次进入多个队列再收集	基数排序
多个增量子表分别插入排序，增量最终为 $1$	希尔排序

35.4 选型与高频陷阱

需求或数据特征	优先考虑	说明
$n$ 小或基本有序	直接插入	简单、稳定、最好 $\Theta(n)$
平均速度快且可接受不稳定	快速排序	实践常用；应随机化或改进枢轴选择降低退化概率
最坏时间必须为 $\Theta(n\log n)$ 且额外空间小	堆排序	原地但不稳定，局部访问性通常不如快排
稳定且最坏 $\Theta(n\log n)$	归并排序	数组需 $O(n)$ 辅助空间，链表尤其合适
记录交换代价远高于比较	简单选择	交换少，但比较仍是 $\Theta(n^2)$
固定位数、取值范围可分桶	基数排序	可突破比较排序下界，但依赖关键字结构
外存文件远大于内存	多路归并	先生成初始归并段，再优化归并路数、段数与归并树

高频陷阱：

折半插入减少比较，不会把最坏记录移动量降到 $O(n\log n)$。
简单选择的比较次数与初始有序度无关；冒泡和直接插入则具有一定自适应性。
快排“枢轴最终就位”不代表左右子区间已经有序。
堆序只约束父子，不能由大根堆直接推出任意兄弟或跨子树结点的大小关系。
归并一个长度为 $n_1$ 与 $n_2$ 的有序段，最多比较 $n_1+n_2-1$ 次，而不是“每个元素最多比较一次”。
稳定算法若实现时错误处理相等关键字，也可能失去稳定性。

教材补充：计数排序

NOTE · 教材范围计数排序不是 2027 年 408 考纲单列的必考算法，但 2027 版常用复习教材把它列为扩展内容。这里补齐算法原理、稳定实现和适用边界，不把它混入原 PDF 内容。

基本思想

若每条记录的整数关键字都落在闭区间 $[L,U]$，令：

$$ k=U-L+1 $$

用 count[x-L] 统计关键字 $x$ 出现次数。仅输出数值时，按关键字从小到大重复输出即可；若记录还带有其他字段且要求稳定性，则需要把计数改成前缀和，再把记录放到独立输出数组。

稳定实现

#include <stdlib.h>
typedef struct { int key; int payload; } Record; // payload 代表随关键字移动的其他字段

// n >= 0，L <= U，k = U-L+1 可由 int 表示；A、B 是互不重叠的 n 元素数组
// Record.key 必须落在 [L, U]；返回 1 表示成功，0 表示内存分配失败
int CountingSort(Record A[], Record B[], int n, int L, int U) {
    int k = U - L + 1;
    int *count = calloc((size_t)k, sizeof *count);
    if (count == NULL) return 0;

    for (int i = 0; i < n; ++i)
        ++count[A[i].key - L];

    for (int i = 1; i < k; ++i)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; --i) {
        int p = A[i].key - L;
        B[--count[p]] = A[i];
    }

    free(count);
    return 1;
}

前缀和 count[p] 表示关键字不大于该键的记录数，也就是该键在输出数组中的右边界后一位。
必须从右向左扫描输入，并在放置前递减计数，才能让原序列中靠右的相等记录落在输出中靠右，从而保持相对次序。
负关键字并不妨碍计数排序，只需统一减去下界 $L$ 作为数组偏移。

复杂度与适用边界

$$ \text{时间}=\Theta(n+k),\qquad \text{额外空间}=\Theta(n+k) $$

若只排序裸整数并直接重复输出，可不设长度为 $n$ 的输出数组，但这种简化不能表达带附属数据记录的稳定性。
计数排序不进行关键字之间的比较，因此不受比较排序 $\Omega(n\log n)$ 下界约束。
它只适合能映射到不太大的离散整数区间的关键字。对浮点数、任意字符串或极稀疏的巨大整数范围，直接开计数数组通常不合适。
基数排序可在每一位内部使用稳定的计数排序；若某一趟不稳定，前面各趟建立的低位次序会被破坏。

35.5 本节复盘

先识别每趟动作，再核验复杂度、空间、稳定性和存储结构，比死记表格可靠。
比较排序最坏比较次数有 $\Omega(n\log n)$ 下界；基数排序依靠关键字分位绕开比较模型。
插入看“扫描已排序区找位置”，选择看“扫描未排序区找极值”。
快排平均快但会退化；堆保证最坏 $n\log n$ 且原地；归并稳定但数组实现需线性辅助空间。
计数排序为 $\Theta(n+k)$，适合值域不大的离散整数键；稳定版本需要前缀和与输出数组。
高频陷阱集中在：折半插入的移动量、希尔增量前提、快排递归深度、堆的局部有序、归并空间和稳定性实现条件。