第 8 章 线性时间排序 (Sorting in Linear Time)
核心结论
-
比较排序下界 (Comparison-Sort Lower Bound)：在判定树 (decision-tree) 模型下，任何比较排序算法在最坏情况下至少需要 \(\Omega(n \lg n)\) 次比较（定理 8.1）；因此归并排序与堆排序是渐近最优的比较排序。
-
计数排序 (Counting Sort)：假设输入元素是 \(0, k\) 范围内的整数；当 \(k = O(n)\) 时，时间为 \(\Theta(n)\)，且是稳定排序 (stable)——关键性质。
-
基数排序 (Radix Sort)：从最低位到最高位依次稳定排序；处理 \(d\) 位、每位 \(k\) 取值的 \(n\) 个数时间为 \(\Theta(d(n+k))\)；当 \(d\) 为常数且 \(k = O(n)\) 时为线性时间。
-
桶排序 (Bucket Sort)：假设输入在 \(0, 1)\) 上均匀分布；分 \(n\) 个桶、桶内插入排序，期望时间 \(\Theta(n)\)。
-
稳定排序 (Stable Sort)：相等元素保持输入顺序——基数排序正确性的关键条件（§8.3），也是计数排序能在 §8.2 后被选为子程序的原因。
-
依赖额外信息突破下界：三种线性时间排序都利用了元素的具体值（不仅是比较），从而突破了比较排序的 \(\Omega(n \lg n)\) 下界。
|
本章主旨
本章是第 2-7 章排序讨论的「下界与替代品」章节。第 8.1 节先给出比较排序的下界——所有只做比较的排序最坏情况下都不可能比 \(\Theta(n \lg n)\) 更快。然后第 8.2-8.4 节给出三种非比较的线性时间排序——计数、基数、桶排序——它们依靠「关于输入的额外信息」（值域在 \(O(n)\) 内、按位分解、均匀分布）换取了线性时间。第 8.3 与 8.4 节还展示了「稳定性」作为子程序性质的应用，以及概率分析（指示变量、期望的二阶矩）。 |
一、核心概念
本章围绕 5 个核心概念展开：先建立比较排序的判定树下界，再给出三种利用额外信息突破下界的算法——计数、基数、桶排序，最后讨论稳定性这一关键子程序性质。
| 概念 | 定义 + 重要性 | 实现提示 |
|---|---|---|
判定树 (Decision Tree) 模型 |
用一棵二叉树抽象一个比较排序的执行路径：内节点 = 一次比较 \(a_i \leq a_j\)，左子树 = 满足比较时的后续路径，右子树 = 不满足时的路径。 |
§8.1；叶数 ≥ \(n!\)；树高 = 最坏比较次数。 |
比较排序的下界 (定理 8.1) |
高度为 \(h\) 的判定树最多有 \(2^h\) 个叶；因为至少 \(n!\) 个叶必须是可达的，故 \(2^h \geq n!\)，由式 3.19 得 \(h \geq \lg(n!) = \Omega(n \lg n)\)。 |
§8.1；定理陈述 + 证明；推论：归并/堆排序渐近最优。 |
计数排序 (Counting Sort) |
对值域在 \(\{0, 1, \ldots, k\}\) 的整数排序：先频次统计，再求前缀和，最后按前缀和指示的位置直接放入输出数组；时间 \(\Theta(n + k)\)；稳定。 |
§8.2；三个循环对应图 8.2 的 (a)(b)(c–f)；最后一遍反向遍历保证稳定性。 |
基数排序 (Radix Sort) |
对 \(d\) 位数从低位到高位依次做稳定排序；引理 8.3：时间 \(\Theta(d(n + k))\)；当 \(d\) 常数且 \(k = O(n)\) 时线性时间。引理 8.4：处理 \(b\) 位整数时按 \(r\) 位一组，时间 \(\Theta((b/r)(n + 2^r))\)，取 \(r \approx \lg n\) 最优。 |
§8.3；伪代码 RADIX-SORT(A, d)；稳定中间排序是关键前提。 |
桶排序 (Bucket Sort) |
假设输入在 \([0,1)\) 均匀分布；分 \(n\) 个桶，每桶用插入排序；期望时间 \(\Theta(n)\)（最坏 \(\Theta(n^2)\)）；与计数排序的「值域假设」相比，桶排序利用的是「分布假设」。 |
§8.4；式 8.1-8.2；指示变量 + 二阶矩公式 = 期望线性。 |
二、详细笔记
8.1 比较排序的下界 (Decision-Tree Lower Bound)
What：用判定树 (decision tree) 这一抽象模型刻画一个比较排序对所有可能的输入执行的所有可能的比较序列；树高 = 最坏情况比较次数。
Why：要证明「任何比较排序都至少需要 \(\Omega(n \lg n)\) 比较」这个下界，必须脱离具体算法、用统一的模型刻画它们。判定树就是这种统一抽象——任何比较排序都能被表示成一棵高度 = 最坏比较次数的判定树。
How：
-
模型定义（§8.1）：
-
内节点 标 i:j，表示一次比较 \(a_i \leq a_j\)；左子树对应 \(a_i \leq a_j\)，右子树对应 \(a_i > a_j\)。
-
叶 标一个排列 \(\langle \pi(1), \pi(2), \ldots, \pi(n) \rangle\)，表示排序结果 \(a_{\pi(1)} \leq a_{\pi(2)} \leq \cdots \leq a_{\pi(n)}\)。
-
关键性质：每个叶必须可达；\(n!\) 个不同排列必须都对应至少一片叶。
-
-
定理 8.1 的证明：设高度 \(h\)，叶数 \(l\)，则 \(l \leq 2^h\)。又 \(l \geq n!\)，故：
\[n! \leq l \leq 2^h \implies h \geq \lg(n!) = \Omega(n \lg n) \quad \text{(由式 3.19)}\] -
推论 8.2：归并排序与堆排序的最坏上界 \(O(n \lg n)\) 与下界匹配，故二者渐近最优的比较排序。
-
计数/基数/桶排序为何能突破下界：它们都不是比较排序——用「元素值」直接索引或分桶，绕开了「只用比较」的假设。
When：当我们希望证明「某些排序不可能做得更快」时；当我们设计算法时，应意识到「如果只用比较，下界在那里」从而寻找额外信息。
Example：对 \(n = 3\)，插入排序的判定树见图 8.1——根节点 i:j = 1:2（比较 \(a_1 \leq a_2\)）；叶数 = \(3! = 6\)，对应 6 种排序结果排列。树高 = 3 = \(\Theta(3 \lg 3)\)。
8.2 计数排序 (Counting Sort)
What：对值域为 \(\{0, 1, \ldots, k\}\) 的 \(n\) 个整数排序——先用辅助数组 \(C[0..k\)] 统计每个值出现次数（频次数组），再求前缀和（≤i 的元素数），最后反向遍历原数组，按 C 给出的位置直接放入输出。
Why：计数排序是「用值换下界」的典型——一旦知道值域是 \(O(n)\)，就能用非比较操作（直接下标访问）做到 \(\Theta(n)\) 时间。它还是稳定排序，是基数排序的关键子程序。
How：
-
伪代码（COUNTING-SORT, §8.2）：
\[\begin{array}{rl} 1 & \textbf{let } C[0{:}k] \textbf{ be a new array} \\ 2 & \textbf{for } i = 0 \textbf{ to } k \\ 3 & \quad C[i] = 0 \\ 4 & \textbf{for } j = 1 \textbf{ to } A.\text{length} \\ 5 & \quad C[A[j]] = C[A[j]] + 1 \\ 6 & \textbf{// } C[i] \textbf{ now contains the number of elements equal to } i. \\ 7 & \textbf{for } i = 1 \textbf{ to } k \\ 8 & \quad C[i] = C[i] + C[i-1] \\ 9 & \textbf{// } C[i] \textbf{ now contains the number of elements } \leq i. \\ 10 & \textbf{for } j = A.\text{length} \textbf{ downto } 1 \\ 11 & \quad B[C[A[j]]] = A[j] \\ 12 & \quad C[A[j]] = C[A[j]] - 1 \end{array}\] -
三段循环分别处理图 8.2 的 (a)、(b)、(c–f)。
-
第 2-3 行：初始化 C 为全 0。
-
第 4-5 行：扫描 A，得到「= i 的元素数」。
-
第 7-8 行：求前缀和，得到「≤ i 的元素数」。
-
第 10-12 行：反向遍历 A，按 C[A[j]] 指示位置放入 B，然后 C[A[j]] 自减——保证相同元素的相对顺序与 A 一致（即稳定性）。
-
-
正确性关键：每放一个 A[j]，C[A[j]] 自减；下一个同值元素的 C 减一，所以排在前一个之后——这就是稳定性。如果改成正向遍历（练习 8.2-3）则不稳定。
When：值域 \(k = O(n)\) 时是首选；不适合 \(k \gg n\) 的情形（辅助空间过大）。
Example：图 8.2 在 A = ⟨2, 5, 3, 0, 2, 3, 0, 3⟩、k = 5 上的执行：(a) C = ⟨2, 0, 2, 3, 0, 1⟩；(b) C = ⟨2, 2, 4, 7, 7, 8⟩；(c-f) 反向遍历依次填入 B 的位置 5→8→6→7→4→2→1→3。
8.3 基数排序 (Radix Sort)
What：从最低位 (least significant digit, LSD) 到最高位 (most significant digit, MSD) 依次稳定排序；处理 \(d\) 位、每位 \(k\) 取值的 \(n\) 个数为 \(\Theta(d(n+k))\)。
Why：直觉上「先排高位再分组递归」更自然，但会产生大量中间堆。LSD 通过「稳定排序」的关键性质避开了这一点——前一位排序的结果被后一位排序时保留下来。在实践中，基数排序是稳定的非比较排序中最常用的；适合整数排序、定长字符串排序、按多键日期排序（年/月/日）。
How：
-
伪代码（RADIX-SORT, §8.3）：
\[\begin{array}{rl} 1 & \textbf{for } i = 1 \textbf{ to } d \\ 2 & \quad \text{use a stable sort to sort array } A \textbf{ on digit } i \end{array}\] -
引理 8.3：每个数字 \(k\) 种取值，稳定排序用 \(\Theta(n+k)\) 时间，总时间 \(\Theta(d(n+k))\)。
-
引理 8.4（处理 \(b\) 位整数）：把每个数视为 \(d = \lceil b/r \rceil\) 个 \(r\) 位的数字，总时间 \(\Theta((b/r)(n + 2^r))\)。
-
当 \(b < \lg n\)：取 \(r = b\)，时间 = \(\Theta(n)\)。
-
当 \(b \geq \lg n\)：取 \(r \approx \lg n\)，时间 = \(\Theta(bn/\lg n)\)。
-
例子：32 位整数当 4 个 8 位数字看（\(b=32, r=8, d=4\)）。
-
-
关键观察：稳定排序是正确性的核心。归纳证明——按位排序时，先把前 i-1 位排好的元素视为「子序列」，第 i 位相同时按稳定排序保持前 i-1 位的顺序。归纳到第 d 位即整体有序。
When：处理整数、字符串等可按位分解的键；当比较代价昂贵时，基数排序优势明显；在内存紧张时不如原地快排（不原地、需要辅助数组）。
Example：图 8.3——对 329, 457, 657, 839, 436, 720, 355 七个数做 LSD 基数排序：(1) 按个位 → 720, 329, 457, 355, 436, 657, 839；(2) 按十位；(3) 按百位 → 整体有序。
8.4 桶排序 (Bucket Sort)
What：假设输入在 \([0, 1)\) 上均匀分布；分 \(n\) 个桶，元素按 \(\lfloor n A[i\) \rfloor] 入桶，桶内插入排序，最后串联输出；期望时间 \(\Theta(n)\)，最坏 \(\Theta(n^2)\)。
Why：与计数排序相比，桶排序利用的是分布假设（均匀）而非值域假设（小范围）。当输入确实均匀时，期望每个桶只有常数个元素，从而得到线性时间。本章也是「指示变量 + 二阶矩 = 期望分析」的精彩演示。
How：
-
伪代码（BUCKET-SORT, §8.4）：
\[\begin{array}{rl} 1 & n = A.\text{length} \\ 2 & \textbf{let } B[0{:}n-1] \textbf{ be a new array} \\ 3 & \textbf{for } i = 0 \textbf{ to } n-1 \\ 4 & \quad \text{make } B[i] \textbf{ an empty list} \\ 5 & \textbf{for } i = 1 \textbf{ to } n \\ 6 & \quad \text{insert } A[i] \textbf{ into list } B[\lfloor n A[i] \rfloor] \\ 7 & \textbf{for } i = 0 \textbf{ to } n-1 \\ 8 & \quad \text{sort list } B[i] \textbf{ with insertion sort} \\ 9 & \quad \text{concatenate the lists } B[0], B[1], \ldots, B[n-1] \end{array}\] -
期望分析（§8.4）：
-
设 \(n_i\) = 桶 \(B[i\)] 中的元素数（随机变量）；运行时间 \(T(n) = \Theta(n) + \sum_{i=0}^{n-1} O(n_i^2)\)。
-
取期望得式 8.1：\(E[T(n)\) = \Theta(n) + \sum_{i=0}^{n-1} O(E[n_i^2])]。
-
用指示变量 \(X_{ij} = I\{A[j\) \in \text{桶 } i\}]；\(E[X_{ij}\) = 1/n]；\(E[X_{ij} X_{ik}\) = 1/n^2]（独立）。
-
展开 \(E[n_i^2\)] = 式 8.3，结果得 \(E[n_i^2\) = 2 - 1/n] = 式 8.2。
-
代入得 \(E[T(n)\) = \Theta(n) + n \cdot O(2 - 1/n) = \Theta(n)]。
-
-
正确性（§8.4）：两个元素 \(A[i\) \leq A[j]]，则桶号 \(\lfloor nA[i\) \rfloor] ≤ \(\lfloor nA[j\) \rfloor]；同桶则插入排序保证顺序，否则按桶号顺序自然就位——所以输出有序。
When：输入确实均匀或近似均匀；处理浮点数、实数（按值分桶）；最坏情况可能比快排慢——但概率保证使其仍是「期望最快」的排序。
Example：图 8.4——A = ⟨.78, .17, .39, .72, .94, .21, .12, .23, .68, .26⟩；分 10 桶 (桶 i ∈ [i/10, (i+1)/10))：(桶 0: .12) (桶 1: .17) (桶 2: .21, .23, .26) (桶 3: .39) (桶 4: .68) (桶 7: .72, .78) (桶 9: .94)；桶内排序 + 串联 → 整体有序。
8.5 稳定性：跨子程序的关键性质
What：稳定排序是指相等键的元素在输出中保持输入中的相对顺序；不稳定排序则可能改变相等元素的相对位置。
Why：稳定性本身并不普遍重要——除非数据带有卫星数据 (satellite data)，否则排序结果中相等元素的相对顺序无所谓。但在 §8.3 基数排序中，稳定性是正确性的前提——如果中间排序不稳定，LSD 排序会得到错误结果。本节不讲新算法，但讨论跨子程序的设计模式。
How：
-
哪些排序是稳定的？
算法 稳定性 插入排序
稳定（逐张插入，保持相对顺序）
归并排序
稳定（合并时左半优先）
堆排序
不稳定（长距离交换可能打乱相等元素）
快速排序
不稳定（PARTITION 的交换是非局部的）
计数排序
稳定（反向遍历 + 自减）
基数排序
取决于中间排序
桶排序
取决于桶内排序（插入排序 → 稳定）
-
用任意排序实现稳定性（练习 8.3-2）：给每个元素附加原始下标作为第二关键字排序——额外 \(O(n)\) 时间 + \(O(n)\) 空间。
When：使用基数排序时必须确认中间排序稳定；处理「带卫星数据」的多键排序（如按年/月/日）时必须稳定。
Example：排序 (3a, 5b, 3c, 1d, 5e)（括号前为键、后为卫星数据）：稳定排序保持 3a 在 3c 前、5b 在 5e 前；不稳定排序可能输出 (3c, 5e, 3a, 1d, 5b)。
三、关键图表
|
本章无独立编号图表
本章的核心算法（计数、基数、桶排序）和判定树、递归树都依赖原书图 8.1–8.5 的图形说明，本笔记以伪代码 + 公式 + 文字描述形式呈现；原书图示可参见 CLRS 第 4 版第 192–212 页。 |
|
核心公式对照表
|
四、思维导图
mindmap
root((第 8 章 线性时间排序))
比较下界
判定树
定理8.1
Ω(n lg n)
计数排序
频次统计
前缀和
反向遍历
稳定
基数排序
LSD优先
引理8.3
引理8.4
r取lg n
桶排序
均匀分布
n个桶
插入排序
期望Θ(n)
稳定性
卫星数据
基数关键
实现方法
额外信息
值域
位分解
分布假设五、重点与易错点
-
判定树模型是「把算法的所有执行路径」抽象为一棵二叉树——这是分析比较排序下界的统一模型。树高 = 最坏比较次数；叶数必须 ≥ \(n!\)。
-
「比较排序下界 ≠ 排序下界」——这是关键澄清。定理 8.1 的下界只在「只用比较」的前提下成立。计数 / 基数 / 桶排序用元素值（不仅是比较）突破下界。
-
计数排序的稳定性来自反向遍历 + C[A[j]] 自减：如果改成正向遍历（练习 8.2-3）则不稳定——稳定性丧失会让它无法用于基数排序。
-
基数排序的关键是 LSD + 稳定中间排序：「先排高位再分组递归」是反直觉但常见错误的算法——会产生指数级中间堆。LSD 反直觉之处在于「先排不重要的位」反而正确——靠稳定排序保留前序结果。
-
基数排序当 \(d\) 为常数 + \(k = O(n)\) 时才是线性时间。如果 \(d \gg 1\)（如大整数）或 \(k \gg n\)（如 64 位键），时间可能远超 \(O(n \lg n)\)。
-
引理 8.4 的最优选择：对 \(b\) 位整数，\(r = \lg n\) 是最优——给「理论用」的最优实践用 r = 8（一个字节）通常就够。
-
桶排序的「期望线性」靠均匀分布假设——现实中这个假设很少严格成立；输入分布接近均匀时表现良好，否则退化为 \(\Theta(n^2)\)。
-
「练习 8.4-2 改进桶排序到 \(O(n \lg n)\) 最坏」：把桶内插入排序换成堆排序或归并排序；常数略增但最坏有界。
-
基数排序不原地——比快排多用 \(O(n)\) 辅助；当内存紧张时倾向快排。
-
指示变量法在桶排序分析中的作用：证明 \(E[n_i^2\) = 2 - 1/n] = 式 8.2——用独立性 + 二阶矩分解（第 5 章工具），是「期望分析」的精彩案例。
-
「稳定性的本质是 TIE 规则」：排序在相等元素上有两类策略——任何一种都可，但「保持原顺序」是最自然的；不稳定排序在小输入可能带来 surprise（同名员工被换岗）。
-
「为什么用 §8.3 不用比较排序 + 复合键」：基数排序避免编写复杂的多键比较函数（如 (year, month, day)）；稳定排序三次分别按 day / month / year 是等效的更简单实现。
-
桶排序 + 链表实现：第 10 章链表将详细介绍；本章假定有维护链表的基本机制（第 10.2 节）。
-
练习 8.2-4（区间计数预处理）：把计数排序思想扩展到「给定 n 个数，问 [a..b] 中有多少个」——预处理 \(\Theta(n + k)\) 后查询 \(O(1)\)。
-
问题 8-2 的原地 0-1 排序：当键只有 0/1 时能同时满足 \(O(n)\) 时间 + 稳定 + 原地三种特性的算法不存在——这是「不可能三角」。
补充：与其他章节的衔接
-
第 2 章：本章的计数 / 基数 / 桶排序都建立在「循环不变量 + RAM 模型」之上；判定树证明采用同样的递归证法。
-
第 6 章：堆排序是 \(\Theta(n \lg n)\) 比较排序的代表；本章定理 8.1 证明它也是渐近最优的。
-
第 7 章：快速排序虽期望 \(\Theta(n \lg n)\)，但最坏 \(\Theta(n^2)\)——不匹配下界，但实践中因为常数因子小仍是首选。
-
第 10 章：桶排序代码用「链表」作为桶的实现——本章假定有此能力，详细见第 10.2 节链表。
-
第 15 章：用基数 / 桶排序做动态规划子问题排序（订单拓扑）是实际工程常见模式；稳定性让多次基数排序保持次序。
-
第 34 章：决策树是第 34 章 NP 完全性证明的工具之一（判定一个串是否属于语言）；本章是最简单的应用。