入门：突破比较排序的 O(n log n) 下限
基于通用算法概念 · 核于 2026-07
速查
- 比较排序下限：任何「只靠两两比较」的排序（快排、归并、堆排、插排……）最坏比较次数 ≥
⌈log₂(n!)⌉ ≈ n log n——这是决策树证明的结论，与具体算法无关，是个硬下限Ω(n log n)。 - 决策树证明思路：
n个元素有n!种可能排列，比较排序每个「比较」把决策树二分一次，区分n!个叶子至少需要高⌈log₂(n!)⌉的树，故比较次数 ≥⌈log₂(n!)⌉ ≈ n log n。 - 非比较排序如何突破：它不比较，而是直接利用数值性质（值域
k、分布、按位分解）来定位元素——绕开了决策树的限制，故能做到线性 O(n)。 - 计数排序（Counting Sort）：统计每个值的出现频次，前缀和后频次变成「该值在结果数组中的末尾下标」，从后往前放置——值域
k时 O(n + k) 时间、O(k) 空间，稳定。 - 桶排序（Bucket Sort）：把值域区间均分成若干桶，元素按值落入对应桶，桶内各自排序后依序拼接——均匀分布时每桶元素少，期望 O(n)，最坏 O(n²)（全挤一个桶）。
- 基数排序（Radix Sort）：把整数按位分解（LSD 从低位到高位），每一位用一趟稳定的计数排序，
d位、基数b时 O(d · (n + b))——稳定性是 LSD 正确的前提。 - 三者共同前提：数据具备可利用的「额外信息」——计数要值域有限、桶要分布均匀、基数要可按位分解且位数不大。没有这些前提，它们不成立。
- 为何不能通用：值域
k远大于n（如 32 位整数）时计数排序空间O(k)爆炸；分布极度不均时桶排序退化；浮点数 / 任意对象不能直接按位分解——所以库默认仍是比较排序。 - 稳定性的关键地位：基数排序要求每一趟（按某一位）稳定，否则高位排序会打乱低位已排好的次序；计数排序若「从后往前放」也是稳定的——稳定性是非比较排序正确性的基石。
- 与比较排序的取舍：数据满足前提 → 非比较排序 O(n) 更快；不满足或不确定 → 比较排序 O(n log n) 通用可靠。工程上非比较排序是「特定场景的加速器」，不是通用替代品。
- 进阶顺序：三种算法详解 → 选型与应用场景 → 参考。
一、比较排序的下限：为什么「只靠比较」最快 O(n log n)
先界定一个重要前提：以下结论只针对比较排序——即「排序的每一步，都是用一次 a[i] < a[j] 这样的比较来决定走向」的算法。快排、归并、堆排、插排、冒泡、选择……全部属于这一类。
决策树证明
任何比较排序都可以建模成一棵决策树（Decision Tree）：
- 每个内部节点代表一次比较
<、>还是=； - 每条从根到叶的路径代表一次排序过程中「比较结果的序列」；
- 每个叶子代表一种「最终输出排列」。
n 个元素共有 n! 种可能的输入排列，因此决策树至少要有 n! 个叶子才能覆盖所有合法输出。一棵二叉树（每次比较二分）若有 L 个叶子，它的高度至少为 ⌈log₂ L⌉。于是最坏情况下比较次数：
最坏比较次数 ≥ 树高 ≥ ⌈log₂(n!)⌉由斯特林公式 n! ≈ (n/e)ⁿ √(2πn)，有：
log₂(n!) = n log₂ n - n log₂ e + O(log n) ≈ n log₂ n - 1.44n所以比较排序的最坏复杂度 Ω(n log n)——这与具体算法无关，是个信息论意义上的硬下限。快排 / 归并 / 堆排都已经达到了这个下界（O(n log n)），靠「改进比较的方式」已经不可能再快了。
关键点：下限只束缚「比较」
注意这个证明的每一个分支都源于「一次比较把可能性二分」。如果一个算法根本不用比较来区分排列，决策树模型就不适用，下限 Ω(n log n) 也就不再束缚它。这正是非比较排序的突破口。
二、非比较排序如何突破下限
非比较排序不把排序看成「比较决策」，而是直接利用数据本身的数值性质来计算每个元素的最终位置。它绕过了决策树的二分限制，所以能做到线性。
| 算法 | 利用的数值性质 | 如何定位元素 |
|---|---|---|
| 计数排序 | 值域 [0, k) 有限 | 统计每个值的频次 → 前缀和 → 频次即末尾下标 |
| 桶排序 | 值分布近似均匀 | 按值落入对应桶 → 桶内排序 → 桶间天然有序 |
| 基数排序 | 整数可按位分解 | 逐位（LSD）用稳定计数排序 → 高位决定最终次序 |
三者的共同模式是：用「值/位/桶」这类直接映射代替「比较」，把定位每个元素的成本从 O(log n)（比较决策）降到 O(1)（算术/下标）。代价是要额外知道 / 假设数据的某些性质（值域、分布、位数），并付出相应的空间。
三、三者各自的前提与代价
非比较排序不是「免费午餐」，每一种都把自己的线性时间建立在某个数据前提之上，前提不满足就退化甚至不可用：
- 计数排序的前提：值域
k与n同阶或更小。要开k+1长度的频次数组，若k ≫ n（如对 10 个 32 位整数排序，k ≈ 4×10⁹），空间与初始化时间O(k)直接爆炸，比比较排序还慢得多。 - 桶排序的前提：值分布近似均匀。均匀时每桶平均
n/m个元素，桶内排序总耗时m · (n/m) log(n/m) = O(n log(n/m))，m与n同阶时期望 O(n)；若分布极度倾斜（全挤一个桶），退化为该桶内排序的复杂度，最坏 O(n²)。 - 基数排序的前提：可按位分解、位数
d不大。它要求元素能拆成d个「位」（整数按十/二进制位、字符串按字符），且d是常数或很小；对任意可比较对象（无法拆位）则无能为力。时间O(d · (n + b))，b是基数。
四、为什么不能通用替代比较排序
正因为前提苛刻，非比较排序在工程里是特定场景的加速器而非通用替代：
- 数据类型受限：计数 / 基数主要面向整数或可映射为整数的类型；浮点数要先映射到桶，任意对象（无法拆位 / 值域无限）则不适用——而比较排序只要有「小于」定义就能用。
- 空间开销：计数排序要 O(k)，桶排序要桶存储 + 桶内数据，基数排序要 O(n + b) 辅助空间——远大于比较排序的 O(1)（堆排）/ O(log n)（快排）。
- 前提难保证：真实数据往往值域大、分布不均、类型异构，非比较排序的前提未必成立，强行使用反而更慢甚至不可用。
所以各语言标准库的默认排序（Array.sort 用 Timsort / V8 的 TimSort+插排、C++ std::sort 用内省排序、Java Arrays.sort 基本类型用双轴快排、对象用 Timsort）仍是比较排序或其混合——非比较排序只在「值域小整数」（如计数排序给小范围整数排序、或作为基数排序的子例程）这类确定满足前提的场景才登场。
五、稳定性的关键地位
非比较排序里稳定性不只是「锦上添花」，而是正确性的前提：
- 基数排序的 LSD 必须稳定：从低位排到高位时，若某一趟不稳定，高位排序就会打乱低位已经排好的相对次序，最终结果错误。所以基数排序内部几乎总是用稳定的计数排序作为子例程。
- 计数排序可稳定：关键技巧是「前缀和 + 从后往前放」——倒序遍历原数组，每个元素放到
count[value] - 1位置并递减计数，这样相同值的元素保持原来的相对次序。 - 桶排序的稳定性取决于桶内：桶间天然有序（按桶号拼接），桶内若用稳定排序则整体稳定，用快排则不稳定。
这条铁律贯穿整个非比较排序章节：要快，先要稳。
下一步
理解了「下限为何成立」与「非比较如何突破」后，下一步逐个拆解三种算法的内部机制——计数排序的「频次 + 前缀和定位」、桶排序的「分桶 + 合并」、基数排序的「LSD 按位 + 稳定子排序」，见三种非比较排序详解。