排序的数学下界：决策树、信息论与 Ω(n log n) 的严格证明

前九篇我们一直在"用"排序、优化排序、甚至决定"不排序"：

1. 《C语言常见排序算法详解》：比较排序的写法、复杂度、稳定性；
2. 《从会写到会用：C语言排序算法的实战选择与优化》：场景选型、qsort 泛型、快排优化；
3. 《突破 O(n log n)：C语言非比较排序实战》：计数/基数/桶排序；
4. 《数据放不进内存怎么办：C语言外部排序与海量数据排序实战》：分块、多路归并；
5. 《让多核一起干活：C语言并行排序与多线程实战》：pthread、OpenMP；
6. 《不只是数字：C语言字符串排序与后缀数组入门》：字符串比较与后缀数组；
7. 《TimSort：工业级排序的秘密》：run 识别、栈式归并、Galloping；
8. 《排序在数据库里到底怎么用》：ORDER BY、Sort-Merge Join、外部聚合；
9. 《排序的边界：什么时候你不该排序》：选择、Top-K、中位数、流式算法。

这九篇反复出现一个论断：

任何基于比较的排序，最坏情况至少需要 Ω(n log n) 次比较。

第 3 篇甚至说"这由决策树模型可以严格证明"，但从未展开。本篇就补上这块理论基石，回答三个问题：

• 这个下界到底怎么证明？
• 它为什么只约束"比较排序"，而计数/基数排序能突破？
• 这个证明对写代码有什么实际指导？

一、先明确：下界约束的是什么？

下界约束的是比较排序：

• 算法只能通过"比较两个元素的大小"获取信息；
• 除了比较结果，算法对元素的值一无所知；
• 不利用元素的值域、位数、分布等额外信息。

计数排序、基数排序、桶排序绕开了"只靠比较"这个前提，所以不受此下界约束——这正是第 3 篇"利用数据额外信息突破下界"的理论依据。

二、决策树模型：把排序算法画成一棵树

2.1 什么是决策树

对固定输入规模 n，任何比较排序算法在给定一组具体输入时，执行路径是一串比较和分支。把所有可能的输入和执行路径画出来，就得到一棵决策树：

• 内部节点：一次比较，如 a[i] < a[j]?，有两个分支（是/否）；
• 叶子节点：一个确定的输出排列（排序结果）；
• 从根到叶的路径：算法对某组输入执行的比较序列；
• 树高：最坏情况下的比较次数。

关键观察：算法要对所有 n! 种输入排列都给出正确的排序结果，所以决策树必须至少有 n! 个叶子（每种排列对应至少一个叶子，否则某个输入会被错误排序）。

2.2 用一个小例子感受

n = 3，元素 a, b, c，共 3! = 6 种排列。一个正确的排序决策树至少要有 6 个叶子。比较排序的决策树是二叉树，高度 h 的二叉树最多有 2^h 个叶子，所以：

2^h ≥ 6 → h ≥ ⌈log₂6⌉ = 3

也就是说，3 个元素最坏至少比较 3 次。插入排序最坏正好 3 次，达到下界。

2.3 推广到一般 n

对 n 个元素：

• 排列数：n!；
• 决策树叶子数 ≥ n!；
• 二叉树高度 h 满足 2^h ≥ n!；
• 所以 h ≥ log₂(n!)。

最坏情况下比较次数 ≥ log₂(n!)，即下界为 Ω(log(n!))。

三、把 log(n!) 化成 n log n

log(n!) 就是我们要的下界，但形式不够直观。用 Stirling 公式或简单放缩即可得到 n log n 量级。

3.1 放缩法（初等证明）

n! = 1 × 2 × … × n。取后一半：

n! ≥ (⌈n/2⌉) × (⌈n/2⌉+1) × … × n ≥ (n/2)^(n/2)

两边取对数：

log₂(n!) ≥ (n/2) · log₂(n/2) = (n/2)(log₂n − 1) = Ω(n log n)

所以 log₂(n!) = Ω(n log n)。

3.2 Stirling 公式（精确渐近）

Stirling 公式给出：

n! ≈ √(2πn) · (n/e)^n

取对数：

log₂(n!) ≈ n log₂n − n log₂e + ½log₂(2πn) = Θ(n log n)

两种方法都得到同一个结论：

任何比较排序，最坏情况比较次数 = Ω(n log n)。

这就是"比较排序下界"的严格证明。

四、下界的三个重要推论

4.1 归并排序和堆排序是"最优"的

归并排序、堆排序最坏都是 O(n log n)，与下界同阶，所以它们是渐近最优的比较排序。快排平均 O(n log n) 但最坏 O(n²)，严格说不是最优（第 2 篇的随机化只是让最坏概率极低，不改变最坏界）。

4.2 不存在"万能更快"的比较排序

下界对所有比较排序成立，不是对某个算法。所以不要幻想"发明一个 O(n) 的比较排序"——数学上不可能。想更快，只有两条路：

• 放弃比较：利用值域/位数/分布（第 3 篇的计数/基数/桶排序）；
• 放松要求：只要 Top-K、中位数、近似结果（第 9 篇的选择、流式算法）。

4.3 平均情况也是 Ω(n log n)

上面的证明针对最坏情况。平均情况同样有 Ω(n log n) 下界（用信息论熵可证），只是常数不同。所以"平均 O(n)"的比较排序也不存在。

五、信息论视角：下界的另一种讲法

决策树是"算法视角"，信息论是"信息视角"，两者殊途同归。

5.1 排序 = 确定是哪种排列

n 个元素有 n! 种可能排列，排序就是从 n! 种可能中确定唯一一种。这需要的信息量是：

log₂(n!) 比特

5.2 一次比较提供多少信息？

一次二选一的比较，最多提供 1 比特信息（是/否）。所以要区分 n! 种排列，至少需要：

log₂(n!) 次比较 = Ω(n log n)

这就是信息论下界：比较是 1 比特的信息获取，排序需要 log(n!) 比特，所以至少 log(n!) 次比较。

5.3 为什么非比较排序能突破？

因为非比较排序每次操作获取多于 1 比特信息：

• 计数排序：直接读元素值当数组下标，一次"读值"获取 log₂k 比特（k 为值域）；
• 基数排序：按位处理，一次"取一位"获取 log₂b 比特（b 为基数）。

它们绕开了"每次比较只给 1 比特"的限制，所以能突破 Ω(n log n)。代价是需要额外信息（值域、位数），这正是第 3 篇反复强调的"适用范围变窄"。

六、下界不是"紧"的：常数与模型

6.1 下界只管阶，不管常数

Ω(n log n) 说的是"至少 n log n 量级"，不告诉你常数是 1 还是 100。工程上常数因子往往比阶更重要——这正是第 2 篇"小数据插入排序常胜出"、第 7 篇"TimSort 在真实数据上快 2~10 倍"的原因。

6.2 下界依赖计算模型

这个下界建立在"比较 + 分支"的计算模型上。若允许更强的操作（如并行比较、字级并行、硬件排序网络），模型变了，下界形式也会变。第 5 篇的并行排序没有突破"总比较次数"下界，但突破了"墙钟时间"——并行改变的是时间，不是工作量。

6.3 外部排序的下界是 I/O 下界

第 4 篇的外部排序，瓶颈从"比较次数"变成"I/O 次数"。外部排序有独立的 I/O 下界：在内存 M、块大小 B 下，排序 N 个元素至少需要 Ω((N/B)·log_{M/B}(N/B)) 次 I/O。这解释了为什么第 4 篇要"增大 k、减少趟数"——那是在逼近 I/O 下界。

七、下界如何指导工程实践

理论不是摆设，下界直接指导选型：

1. 别追求不存在的算法：想比 O(n log n) 快，先问"能不能不比较"（第 3 篇）或"能不能不要全序"（第 9 篇）。
2. O(n log n) 已是最优时，优化常数：归并/堆排已达下界，再优化只能降常数（缓存友好、分支预测、SIMD）。
3. 非比较排序要看前提：计数排序 O(n+k) 在 k 很大时不如 O(n log n)，下界不约束它，但工程约束它（第 3 篇的"k 过大内存爆炸"）。
4. 并行不改工作量：第 5 篇的并行排序总比较次数不变，只是分摊到多核。想减少总工作量，得换算法，不是加线程。
5. 外部排序看 I/O 下界：第 4 篇的调 k、调块大小，本质是在逼近 I/O 下界，而非比较下界。

八、常见误区与检查清单

1. “快排平均 O(n log n) 所以最优”：平均最优不等于最坏最优，快排最坏 O(n²)，归并/堆排才是最坏最优。
2. “基数排序 O(n) 所以吊打快排”：前提是位数有限、值域可控，否则常数和空间开销更大（第 3 篇）。
3. “下界说明排序没法更快”：下界只约束比较排序，非比较排序和"不要全序"都能突破（第 3、9 篇）。
4. “并行能突破下界”：并行降低墙钟时间，不降低总比较次数，下界依然成立（第 5 篇）。
5. “log(n!) 约等于 n log n 所以精确”：这是渐近等价，常数项（−n log e）在 n 小时不可忽略。
6. “决策树证明只对最坏情况”：平均情况同样有 Ω(n log n) 下界，只是证明用熵而非树高。
7. “下界意味着实现都该一样快”：下界是阶，常数、缓存、分支预测决定实际快慢。

九、小结与系列脉络

本篇是系列的"理论收束"：前九篇反复引用的下界，在这里被严格证明。

• 第 1 篇：比较排序的复杂度表，现在有了理论依据——O(n log n) 不是巧合，是下界；
• 第 2 篇：快排优化只在降常数，因为阶已达下界附近，无法再降；
• 第 3 篇：非比较排序能突破，因为绕开了"每次比较 1 比特"的信息限制；
• 第 4 篇：外部排序的 I/O 下界是另一个模型下的下界，与比较下界平行；
• 第 5 篇：并行排序不改变总比较次数，下界依然成立；
• 第 9 篇：选择/Top-K/中位数能到 O(n)，因为它们不需要全序，绕开了 log(n!) 的信息量。

一句话心法：Ω(n log n) 是"获取全序信息"的代价，不是"排序"的代价。想更快，要么少获取信息（不要全序），要么每次获取更多信息（非比较）。

至此系列十篇：

1. 原理：七种比较排序的写法与复杂度；
2. 实战：场景选型、泛型 qsort、快排优化、性能测试；
3. 突破：计数/基数/桶排序，突破 Ω(n log n)；
4. 规模：外部排序与多路归并，矛盾转向 I/O；
5. 并发：并行排序与多线程，榨干多核；
6. 对象：字符串排序与后缀数组，从"排数字"到"排结构"；
7. 工业：TimSort，真实数据的最优解；
8. 系统：数据库中的排序，算法在真实系统里的位置；
9. 边界：什么时候不该排序，选择、Top-K、中位数与流式算法；
10. 理论：决策树、信息论与 Ω(n log n) 的严格证明。

从"怎么写"到"为什么不能更快"，这条线完成了对排序最完整的认知闭环：会写是基础，会选是进阶，会优化是工程，懂下界是内功。