为什么基于比较的排序最坏至少需要 O(n log n)？
简化版
基于比较的排序只能通过两两比较获得元素顺序信息。
对 n 个不同元素，可能的排列有 n! 种。比较过程可以看成一棵二叉决策树，每次比较只有「小于」或「大于」两种分支。为了区分所有 n! 种排列，决策树叶子至少有 n! 个，所以高度至少是 log2(n!)，约等于 O(n log n)。
因此比较排序的最坏时间复杂度不可能突破 O(n log n)。
详细版
排序算法最终要确定输入属于哪一种排列。
如果算法只靠比较，那么每次比较最多把可能性分成两类。整个过程可以抽象成决策树：
compare a[i] and a[j]
├─ a[i] < a[j]
└─ a[i] > a[j]n 个互不相同元素有 n! 种排列。决策树至少要有 n! 个叶子才能覆盖所有答案。
| 推导 | 含义 |
|---|---|
叶子数至少 n! | 每种排列一个结果 |
高度至少 log2(n!) | 最坏比较次数 |
log2(n!) = Θ(n log n) | 比较排序下界 |
这解释了为什么归并、堆排序能做到 O(n log n)，已经达到比较排序的渐进最优。
完整版教学
1. 什么叫基于比较的排序
基于比较的排序，指算法只能通过比较两个元素来判断它们的相对顺序。
典型例子包括：
- 冒泡排序；
- 插入排序；
- 选择排序；
- 快速排序；
- 归并排序；
- 堆排序。
它们不直接利用元素值的范围、位数或分布，只问类似这样的问题：
a[i] < a[j] ?2. 排序要区分多少种可能
如果 n 个元素互不相同，那么输入顺序可能有：
n!种。
排序算法必须把每一种输入排列映射到正确的输出顺序。如果两个不同排列在比较过程中完全走了同一条路径，算法就无法区分它们。
排序的本质是从大量可能排列中识别出当前输入对应的那一个。
3. 为什么能用决策树建模
每次比较两个元素，结果通常只有两类：
x < y
x > y如果考虑相等元素，会多一些细节，但下界分析通常先看互异元素。
把每次比较作为树上的一个分叉，就得到一棵二叉决策树。根节点是第一次比较，叶子节点是算法给出的最终排列结论。
4. 决策树叶子为什么至少 n!
每一个可能输入排列都必须对应一个正确的叶子。
如果叶子数量少于 n!，就说明至少有两个排列落到同一个叶子，算法无法对它们给出不同判断。
所以：
leaves >= n!而一棵高度为 h 的二叉树，最多有：
2^h个叶子。
5. 如何推出 log(n!)
由：
2^h >= n!两边取对数：
h >= log2(n!)这个 h 就是最坏情况下需要的比较次数下界。
利用 Stirling 公式可以得到：
log(n!) = Θ(n log n)所以比较排序的最坏复杂度下界是 Ω(n log n)。
6. 这和实际排序算法有什么关系
归并排序和堆排序最坏时间复杂度都是：
O(n log n)它们已经达到比较排序模型下的渐进最优。
快速排序平均是 O(n log n)，但最坏可能退化到 O(n^2)，所以它平均很强，但最坏不如归并和堆排序稳定。
7. 非比较排序为什么能突破
计数排序、桶排序、基数排序可以在线性时间完成，是因为它们不只靠比较。
它们利用了额外信息：
| 算法 | 利用的信息 |
|---|---|
| 计数排序 | 值域范围 |
| 桶排序 | 数据分布 |
| 基数排序 | 位数或字符位 |
这类算法突破的是「比较排序模型」的限制，而不是推翻下界证明。
8. 常见误区与追问
- 误区：所有排序都不可能快于
O(n log n)。 这个下界只针对基于比较的排序，非比较排序在特定条件下可以更快。 - 误区：平均复杂度和最坏下界是一回事。 决策树推的是最坏比较次数下界。
- 误区：快速排序平均最快，所以突破了下界。 快排平均仍是
O(n log n)，没有突破比较排序下界。 - 追问：为什么叶子要至少有
n!个？ 因为每种输入排列都需要被区分并得到正确顺序。 - 追问：归并排序是不是最优？ 在比较排序模型下，归并排序最坏
O(n log n)已经达到渐进最优。