一、比较排序的下界
问题：归并、堆、快排都是 Θ(n log n)。是我们还没想到更好的算法，还是这就是极限？
答案取决于允许做什么操作。 前面所有算法只通过比较获取信息（a[i] < a[j]?），这类算法称为比较排序（comparison sort）。对它们，Θ(n log n) 就是极限。
决策树模型
把一个比较排序算法在规模为 n 的所有输入上的执行，画成一棵决策树：
- 内部节点 标记为
i : j，表示"比较 a[i] 与 a[j]" - 两条出边 对应比较的两种结果
- 叶节点 是一个排列，表示算法输出的顺序
n = 3 的决策树：
1:2
≤ ╱ ╲ >
╱ ╲
2:3 1:3
≤╱ ╲> ≤╱ ╲>
⟨123⟩ 1:3 ⟨213⟩ 2:3
≤╱ ╲> ≤╱ ╲>
⟨132⟩ ⟨312⟩ ⟨231⟩ ⟨321⟩
叶子数 = 6 = 3!
最长路径 = 3 次比较
两个观察：
- 每个可能的输出排列都必须至少对应一片叶子。否则存在某个输入，算法给不出正确答案。所以 叶子数 L ≥ n!。
- 算法在某个输入上的比较次数 = 从根到对应叶子的路径长度。因此最坏情况比较次数 = 树高 h。
定理与证明
定理：任何比较排序在最坏情况下都需要 Ω(n log n) 次比较。
证明：一棵高度为 h 的二叉树最多有 2^h 片叶子。结合 L ≥ n!：
2^h ≥ L ≥ n!
h ≥ log₂(n!)
由 Stirling 近似（第 2 讲）：
n! ≈ √(2πn)·(n/e)ⁿ
log₂(n!) = n log₂ n − n log₂ e + O(log n) = Θ(n log n)
⟹ h = Ω(n log n) ∎
推论：归并排序和堆排序是渐近最优的比较排序。
⭐ 下界的信息论解读
换一个角度看这个证明，它其实非常直观：
需要区分的可能答案数：n! 种排列
每次比较获得的信息： 1 比特（两种结果之一）
⟹ 至少需要 log₂(n!) ≈ n log₂ n 比特的信息
⟹ 至少需要 n log₂ n 次比较
排序的本质是「确定输入是哪一个排列」，而比较是一次只能问一个是非问题的信道。 n log n 是这个信道的信息论极限，与算法的聪明程度无关。
n = 100 时下界约 525 次比较；归并排序实际用约 550 次，快排约 730 次——都已经很接近极限了。
⚠️ 下界成立的前提
这个下界只对比较排序成立。它假设算法获取信息的唯一手段是比较。
如果允许别的操作呢？ 比如"直接用键值做数组下标"——这一步不是比较，而是直接寻址，它一次获取的信息远多于 1 比特。下面三种算法正是这么做的。
二、计数排序
额外假设：键是 [0, k) 范围内的整数，且 k = O(n)。
思想：不比较，而是数每个值出现了多少次，再由此算出每个元素的最终位置。
func CountingSort(a []int, k int) []int {
count := make([]int, k)
for _, x := range a { // ① 统计每个值的出现次数
count[x]++
}
for i := 1; i < k; i++ { // ② 前缀和：count[i] = 值 ≤ i 的元素个数
count[i] += count[i-1]
}
out := make([]int, len(a))
for i := len(a) - 1; i >= 0; i-- { // ③ ⚠️ 必须倒序遍历才稳定
count[a[i]]--
out[count[a[i]]] = a[i]
}
return out
}
输入 a = [2, 5, 3, 0, 2, 3, 0, 3]，k = 6
① 计数： count = [2, 0, 2, 3, 0, 1]
0 1 2 3 4 5
② 前缀和： count = [2, 2, 4, 7, 7, 8]
含义：值 ≤ 3 的有 7 个 ⟹ 最后一个 3 应放在下标 6
③ 倒序填充： out = [0, 0, 2, 2, 3, 3, 3, 5]
| 性质 | 值 |
|---|---|
| 时间 | Θ(n + k) |
| 空间 | Θ(n + k) |
| 稳定 | ✓（第 ③ 步倒序遍历） |
⭐ 为什么第 ③ 步必须倒序？ 前缀和给出的是每个值的最后一个位置。倒序遍历输入时，同值元素中原本靠后的先被放置，占据靠后的位置——原有相对顺序得以保持。正序遍历会得到正确但不稳定的结果，而稳定性正是计数排序作为基数排序子过程的前提。
⚠️ k 必须与 n 同量级。 排序 100 个 32 位整数时 k = 2³²，需要 16 GB 的计数数组——完全不可行。
三、基数排序
解决计数排序的 k 太大问题：不一次排整个键，而是按位分组，逐位排。
关键决策：必须从最低位（LSD）开始，且每一趟必须用稳定排序。
输入 按个位排 按十位排 按百位排
329 720 720 329
457 355 329 355
657 436 436 436
839 ──▶ 457 ──▶ 839 ──▶ 457
436 657 355 657
720 329 457 720
355 839 657 839
// 按 32 位无符号整数排序，每轮处理 8 位，共 4 轮
func RadixSort(a []uint32) []uint32 {
const bits, radix = 8, 1 << 8
buf := make([]uint32, len(a))
count := make([]int, radix)
for shift := 0; shift < 32; shift += bits {
for i := range count {
count[i] = 0
}
for _, x := range a {
count[(x>>shift)&(radix-1)]++
}
for i := 1; i < radix; i++ {
count[i] += count[i-1]
}
for i := len(a) - 1; i >= 0; i-- { // 稳定：倒序
d := (a[i] >> shift) & (radix - 1)
count[d]--
buf[count[d]] = a[i]
}
a, buf = buf, a // 交换缓冲区
}
return a
}
复杂度：d 轮，每轮 Θ(n + radix)：
T(n) = Θ(d · (n + radix))
对 b 位的键、每轮 r 位：d = b/r，radix = 2^r：
T(n) = Θ((b/r)(n + 2^r))
r 的选择：r 太小则轮数多，r 太大则计数数组太大。渐近上取 r = Θ(log n)（使 2^r = Θ(n)，两项平衡）即得
T(n) = Θ(b·n / log n)
⚠️ 但「取 r = log₂ n」是渐近指导，不是具体参数下的最优值，实践中还有两条硬约束：
| 约束 | 后果 |
|---|---|
| 轮数 b/r 必须是整数 | 32 位键只能取 r ∈ {8, 11, 16}（4、3、2 趟）；r = 20 意味着 1.6 趟，无法实现 |
| ⭐ 计数数组必须放得进缓存 | 2^11 × 4B = 8 KB 稳进 L1；2^16 × 4B = 256 KB 已溢出 L2。计数阶段是随机写，一旦超出缓存，每次自增都是一次未命中 |
实算（b = 32、n = 10⁶，代入 T(r) = (32/r)(n + 2^r)）：
r = 8 4.00 趟 计数数组 256 T = 4.00×10⁶
r = 11 2.91 趟 计数数组 2 048 T = 2.92×10⁶ ← 实践常用（L1 友好）
r = 16 2.00 趟 计数数组 65 536 T = 2.13×10⁶ ← 公式与整数趟数的最佳折中
r = 17 1.88 趟 计数数组 131 072 T = 2.13×10⁶ ← 公式的最小值点
r = 20 1.60 趟 计数数组 1.05×10⁶ T = 3.28×10⁶ ← ⚠️ 比 r=16 差 1.5 倍
⭐ 注意 r = log₂ n = 20 反而比 r = 16 差 50%：2^r 是指数增长的，一旦它超过 n，计数数组的开销就迅速压倒省下的那部分轮数。渐近公式给出的是量级，不是最优参数——具体取值必须代入数字算，并结合缓存实测。 这正是第 2 讲「渐近分析骗你的时候」那一节的又一个实例。
⭐ 为什么必须从低位开始、必须稳定
从高位开始（MSD） 也可以，但需要对每个桶递归处理，实现复杂得多（不过 MSD 适合变长字符串，且能提前终止）。
LSD 的正确性完全依赖稳定性：处理第 i 位时，前 i−1 位已经排好；稳定排序保证第 i 位相同的元素保持它们按低位排好的顺序。用不稳定排序做某一轮，前面所有轮的工作都会被打乱。
这是"稳定性"在算法中真正不可替代的一次出场（第 9 讲）。
⚠️ 符号与浮点的处理：有符号整数要先做偏移（x ^ 0x80000000）才能按无符号比较；IEEE 754 浮点数需要一次位变换（正数翻符号位、负数全翻）才能保序。
四、桶排序
额外假设：输入均匀分布在某个区间上（如 [0,1) 的均匀随机数）。
func BucketSort(a []float64) {
n := len(a)
buckets := make([][]float64, n)
for _, x := range a { // 期望每桶 1 个元素
i := int(float64(n) * x)
buckets[i] = append(buckets[i], x)
}
idx := 0
for i := range buckets {
InsertionSort(buckets[i]) // 桶内元素少，插入排序最合适
for _, x := range buckets[i] {
a[idx] = x
idx++
}
}
}
分析：设 nᵢ 为第 i 个桶的元素数，桶内用插入排序：
E[T(n)] = Θ(n) + Σᵢ E[O(nᵢ²)]
在均匀分布假设下，nᵢ 服从二项分布 B(n, 1/n)，可以算出 E[nᵢ²] = 2 − 1/n：
E[T(n)] = Θ(n) + n·O(2 − 1/n) = Θ(n) ∎
⚠️ 对分布假设极其敏感。所有元素落进同一个桶时退化为 Θ(n²)。实际使用前必须了解数据分布，否则风险很大。
五、三者对比与选型
| 算法 | 时间 | 空间 | 稳定 | 额外假设 |
|---|---|---|---|---|
| 计数排序 | Θ(n + k) | Θ(n + k) | ✓ | 键是 [0,k) 的整数，k = O(n) |
| 基数排序 | Θ(d(n + radix)) | Θ(n + radix) | ✓ | 键可按位分解且定长 |
| 桶排序 | 期望 Θ(n)，最坏 Θ(n²) | Θ(n) | 取决于桶内排序 | 输入均匀分布 |
⭐ 它们并没有"打破"下界，而是不在下界的适用范围内。 下界针对的是"只能比较"的算法；这三种都用了键的内部结构（数值范围、位表示、分布），因此获取信息的速率高于 1 比特/操作。
天下没有免费的午餐：每一种线性排序都用一个额外假设换来了速度。假设不成立时，它们比 Θ(n log n) 的通用排序糟糕得多。
什么时候真的该用它们
| 场景 | 选择 |
|---|---|
| 排序年龄、评分、状态码（值域几百） | 计数排序 |
| 排序大量 32/64 位整数或定长字符串 | 基数排序（比 quicksort 快 2–3 倍） |
| 数据库按整型主键排序 | 基数排序 |
| 已知均匀分布的浮点数 | 桶排序 |
| 其他一切情况 | Θ(n log n) 的通用排序 |
一个真实数据点：现代 LSD 基数排序（如 ska_sort、radsort）排序 10⁷ 个 32 位整数通常比 std::sort 快 2–4 倍。但它排不了任意 Less 函数定义的顺序——这才是通用排序不可替代的原因。
六、下界的其他形式
Ω(n log n) 只是最基本的一个。同一套决策树论证还能给出：
| 结论 | 下界 |
|---|---|
| 比较排序（最坏） | Ω(n log n) 次比较 |
| 比较排序（期望，含随机化） | Ω(n log n) |
| 在有序数组中查找（比较模型） | Ω(log n)（二分查找最优） |
| 求最大值 | 恰好 n − 1 次比较 |
| 同时求最大与最小值 | ⌈3n/2⌉ − 2 次比较（成对处理） |
| 求第二大 | n + ⌈log₂ n⌉ − 2 次（锦标赛法） |
| 中位数选择（比较模型） | Ω(n)（第 13 讲可达到） |
⭐ 注意随机化不能打破排序下界：决策树论证对随机化算法同样适用（取所有随机串上的平均树高）。这与第 11 讲的结论一致——随机化能让快排避开最坏情况，但不能让它跑得比 n log n 更快。
随堂自测
- 决策树模型中，叶子数为什么至少是 n!？树高对应什么？
- 完整写出 Ω(n log n) 下界的证明，指出用到 Stirling 近似的位置。
- 从信息论角度重述这个下界：为什么"每次比较得到 1 比特"是关键？
- 这个下界对基数排序不成立，是因为基数排序更聪明，还是因为它不在模型内？说清楚区别。
- 计数排序第三步为什么必须倒序遍历？正序会破坏什么？举一个具体例子。
- 基数排序为什么必须使用稳定的子排序？用一个 2 位数的例子说明不稳定会出什么错。
- 用基数排序排 n = 10⁶ 个 32 位整数，每轮取 r 位。写出复杂度关于 r 的表达式并求最优 r。
- 桶排序的期望 Θ(n) 依赖什么假设？构造一个使它退化为 Θ(n²) 的输入。
- 为什么随机化不能打破 Ω(n log n)？