前年年底对账,有个需求是把一百万条订单按金额排序,再取前五千条人工复核。线上用语言自带的排序,本机拿同规模数据对照,一次约 171 毫秒。有人提议自己写:只排数字,不要通用比较函数,理论上能快一个数量级,目标二十毫秒。

改了三版,最好的一版比内置快了不到三成。把比较次数打印出来才看清:两边都在两千万次上下,差距只在每次比较做了多少事。想快十倍,靠换写法做不到,因为比较排序有一个由信息量算出来的地板。

这篇就从这个地板讲起。先把「快十倍」拆成比较次数和每次比较的成本两件事,再用决策树数清楚为什么 n 个元素至少要 log2(n!) 次比较,接着用斯特林公式把它算成 n log2 n,最后说明这个下界只管只靠比较的排序:计数和桶排序靠额外空间与值域信息绕开它。

现场:快十倍的目标,卡在哪里

先统一两个词。比较排序指只通过「两个元素谁大谁小」获取信息的排序,归并、快排、堆排、插入都属于这一类。比较次数指做了多少次大小判断,不含下标运算、赋值和调用。下界约束的是前者,你能优化的往往只有后者。

「自己写肯定更快」的直觉来自一个真实的对比:标准库要处理任意类型、调用用户比较函数、保证稳定性,听起来处处是开销;我只排数字,应该快很多。这个直觉只对一半:砍掉通用性省的是常数时间,省不掉比较次数,因为两者都在用比较区分 n! 种排列。

本机做过一组对照:一百万个 0 到 999 的整数,内置排序约 171.1 毫秒,计数排序约 3.9 毫秒,差了四十四倍。差距不是代码更巧,而是计数排序根本没做「谁大谁小」,它直接把值当下标去数次数。一边比较,一边查表,模型的差别远大于写法。

反过来,只要留在比较模型里,就绕不开这个量级。本机让归并排序排一万个随机整数,比较 120319 次,而一万个元素的整数下界是 118459 次,只差百分之一点六。一个规规矩矩的归并排序已经把地板贴得很紧,继续优化最多只能抹掉这一点余量。

一次比较排序在信息上做了什么
输入 n 个元素,共有 n! 种排列
每次比较只有两种结果,最多砍掉一半候选
重复砍半,直到只剩一种排列
砍了多少次,就是比较次数的下界

这四步就是全文的主线。把它写成数学,就能得到一个和具体算法无关的数字:不管用快排、归并还是堆排,只要只靠比较,最坏情况下都不可能比这个数字更少。

决策树:把排序过程画成一棵二叉树

决策树(decision tree)在这里不是机器学习里的那个模型,而是一种描述算法行为的图:每个内部节点代表一次比较,节点分出两条边,左边代表比较结果为「是」,右边代表「否」,叶子代表算法最终输出的排列。排序算法每跑一次,就是在这棵树里从根走到某个叶子。

为什么叶子至少要 n! 个?n 个互不相同的元素一共有 n! 种排列(n 的阶乘)。排序算法对每一种排列都必须给出正确结果,而两种不同的输入排列排好后的顺序也不同。如果它们落在同一个叶子,算法只能输出一种顺序,必然排错其中一种。所以树至少要有 n! 个叶子。

一棵高度为 h 的二叉树最多有 2 的 h 次方个叶子:从根往下走 h 步,每一步两种选择,路径最多 2 的 h 次方条。要让叶子不少于 n!,就必须 2 的 h 次方大于等于 n!,两边取以 2 为底的对数,得到 h 大于等于 log2(n!)。这个 h 就是最坏输入下的比较次数。

输入有多少种n 个不同元素有 n! 种排列,每一种都必须被正确区分,不能合并。
一次比较给多少信息只有「是」和「否」两个结果,相当于一位二进制信息,最多把候选集合砍成两半。
需要多少层把 n! 个候选砍到 1 个,至少要 log2(n!) 层,这就是比较次数的下界。

拿 n 等于 3 验证。3 个元素有 6 种排列,log2(6) 约等于 2.58,向上取整是 3,所以至少要比较 3 次;插入排序排 3 个元素最坏正好比较 3 次,贴着下界。再看 n 等于 4,log2(24) 约等于 4.58,向上取整是 5;插入排序最坏比较 6 次,多出来的一次就是算法留下的余量。

这里有两个容易误读的地方。第一,下界是对所有输入的最坏情况,不是对某一个输入:数据已经有序时插入排序只比较 n 减 1 次,远低于 log2(n!),这并不矛盾,那种输入本来就简单。第二,下界不是快排的下界,而是所有比较排序的下界,换算法跑不掉,换前提才有用。

平均情况也受同一个数字约束:把 n! 个叶子摆在二叉树上让平均深度最小,最紧凑的摆法接近满二叉树,平均深度同样在 log2(n!) 附近。所以最坏和平均都不会比它低太多。

斯特林公式:log2(n!) 到底有多大

log2(n!) 这个写法很准确,但没法直接心算。斯特林公式(Stirling's approximation)给了它一个可计算的近似:ln(n!) 约等于 n 乘 ln(n) 减 n,再加二分之一乘 ln(2πn)。把自然对数换成以 2 为底,用到换底常数 log2(e) 约等于 1.4427,就得到 log2(n!) 约等于 n 乘 log2(n) 减 1.4427 乘 n,后面还可以再加一个很小的修正项。

把 n 从 10 一直代到 100 万,用循环累加 log2(i) 得到的精确值和公式值放在一起,差距一眼就能看出来。下表里的「至少比较次数」是对精确值向上取整,因为比较次数必须是整数。

nlog2(n!) 精确值至少比较次数斯特林前两项
1021.79112218.79
100524.7650525520.12
10008529.398085308523.09
10000118458.1430118459118450.17
1000001516704.173915167051516694.54
100000018488884.82001848888518488873.53

小 n 时公式偏低,是因为省掉了后面的修正项。n 等于 10 时修正项贡献约 2.96,加上去是 21.75,接近精确值 21.79;n 等于 100 万时修正项只有十几,相对一千八百多万可以忽略。记结论时直接用 n log2 n 减 1.4427n,算大数够用。

这张表最该记住的是最后一行:一百万个元素至少要做一千八百四十九万次比较。每秒一亿次比较,光比较就要 0.18 秒,还没算数据搬运。内置排序 171 毫秒已经贴着下限在跑;想压到 17 毫秒,等于每秒十亿次比较,单线程做不到。

为什么换算法也击不穿地板

理解了决策树,就能明白不同算法的差别在哪。归并排序每次比较都能把两个有序段里的候选缩小一个,比较次数接近下界;快排每次划分把每个元素和 pivot 比一次,平均约 1.39 乘 n 乘 log2(n),比下界多约四成常数;堆排也在 n log2 n 量级,常数更大。它们的差别是常数因子,不是阶。

常数因子当然值得优化。比较函数内联、减少分支预测失败、让数据待在缓存里、把递归改成循环,都能省时间。本机那个归并只比下界多百分之一点六,比较次数几乎没有水分;可它仍可能比内置慢,因为比较之外还有切片、分配和回收。

所以「快一个数量级」在同一个模型里不成立。你可以把 171 毫秒压到 80 毫秒,但压不到 17 毫秒,因为那要求比较次数降到两百万以下,而地板是一千八百四十九万。要跨过门槛只有三条路:换掉比较模型;用并行分摊;先过滤减少数据。唯独把同样的比较写得更漂亮不是。

下界约束的是比较次数,不是墙钟时间。并行排序可以让总时间低于单线程跑完下界所需的时间,但所有核加起来做的比较次数仍然不会低于这个数字。讨论下界时,先确认大家在说同一个度量。

计数排序与桶排序:用空间和值域绕开下界

下界的推导有一个隐藏前提:算法只能通过比较获取信息。前提不成立,下界也就不适用。计数排序(counting sort)就是最直接的例子:它假设待排的都是整数,值落在 0 到 k 之间,于是开一个长度为 k 加 1 的数组,记下每个值出现的次数,再按值从小到大把次数展开成有序序列。

function countingSort(a, k) {
  const count = new Int32Array(k + 1);
  for (let i = 0; i < a.length; i++) count[a[i]]++;
  for (let i = 1; i <= k; i++) count[i] += count[i - 1];
  const out = new Int32Array(a.length);
  for (let i = a.length - 1; i >= 0; i--) out[--count[a[i]]] = a[i];
  return out;
}

这段代码里没有任何大小判断,只有加一、累加和按下标写回。时间成本是 n 加 k,空间成本也是 n 加 k。k 和 n 同量级时整体线性,所以它能比下界快。本机那一百万个整数,计数排序 3.9 毫秒,比较排序 171.1 毫秒,四十四倍就来自这里。

代价也很硬。k 是值域大小,不是元素个数。如果订单金额以分为单位、最大一亿元,k 就是一亿,计数数组要占几百兆字节,还没开始排序内存就先满了。所以计数排序适合年龄、分数、状态码这种取值范围小的整数,不适合金额、时间戳这种范围巨大的键。

桶排序把值域切成若干区间,每个区间一个桶,元素按值落桶,再对桶内排序。数据均匀时,每个桶约装 n 除以桶数个元素,整体平均线性;全挤进一个桶时,就退化成对一个桶做普通排序,最坏回到平方级。它比计数排序宽容,不要求每个可能值开格子,但仍要知道值域并接受分布假设。

基数排序(radix sort)把所有键看成固定位数的数字,从最低位开始,每一轮按一位做一次计数排序,做完所有位就整体有序。它要做 d 轮,每轮成本 n 加基数 b。对 32 位整数用 8 位一组,d 等于 4,b 等于 256,四轮排完,不需要一亿个计数器。

比较排序

只靠大小判断获取信息,适用于任意可比较的类型,不需要知道值域。最坏受 log2(n!) 约束,一百万个元素至少一千八百四十九万次比较。优点是通用、容易做稳定版本、额外空间少。

非比较排序

直接读取键的位或值,用下标定位,不产生大小判断。计数、桶、基数排序在合适条件下能做到线性。代价是必须知道值域或分布,通常要额外空间,浮点和字符串还要先编码成整数。

这张对比不是「新方法打败旧方法」,而是「两种前提下的最优解」。值域小、数据量大、内存够,计数或基数排序赢;类型任意、值域未知,比较排序仍是默认选择。下界没有被推翻,只是在自己的前提内成立。

现象、原因与第一步排查

排序性能的问题常被说成「这个排序慢」,但慢的原因完全可能不在算法里。下面这些现象都来自比较排序的成本模型,先按表里的第一步定位,不要急着换算法。

现象真实原因第一步查什么
手写快排比内置排序慢一倍内置排序是混合算法,常数项更小,比较次数本来就接近下界给比较函数加计数器,先比次数再比耗时
换个语言重写,只快了不到三成比较次数由下界决定,换语言只改常数,不改阶算出理论上界与实测次数的差距
宣称自己的排序快十倍测试数据有界或近似有序,利用了值域或适应性换随机数据、有序数据、重复数据各测一遍
计数排序在金额数据上内存爆掉计数数组按值域分配,值域远大于元素个数先看最大值与最小值之差,再估算内存
桶排序某个桶排了很久数据分布倾斜,绝大多数元素落进同一个桶抽样统计每个桶的元素数量
加了多线程反而更慢数据量小,线程创建和合并的开销超过收益先测单线程耗时,再算并行加速比
字符串排序比数字慢很多一次比较要逐字符比,单次比较成本不是常数统计实际比较次数与平均字符比较长度
结果里相等元素的先后顺序变了用了不稳定的排序,相等键的相对次序被打乱确认业务是否需要稳定,必要时加次序键

表里最容易被忽略的是第二行和第四行。第二行把「常数优化」误当成「算法升级」,测完只快三成却找不到原因;第四行把「元素个数」和「值域大小」混为一谈,看到一百万条数据就以为计数数组只要一百万格。判断方案时,先问数据类型、值域多大、能否用额外空间,再谈算法。

边界与代价:下界不承诺时间

下界说的是比较次数,不是毫秒数。同样的次数,比较两个整数和两个长字符串能差几个数量级。字符串要逐字符看,公共前缀越长越贵;键是对象还要先取字段。这时减少比较次数仍有意义,但比较本身的成本可能才是主要矛盾,比如先把字符串转成短编码。

下界也不承诺空间。归并排序比较次数贴近下界,代价是额外一块和原数组同量级的空间;快排原地,额外空间是对数级递归栈,但比较次数多一点,还可能退化;堆排原地、最坏也是 n log2 n,可常数大、缓存不友好。选哪个取决于你更在意时间、内存还是稳定性,而不是谁更接近下界。

还有一个常被忘掉的边界:数据量和常数。n 很小时,log2(n!) 只有几十次比较,算法差距被函数调用淹没,插入排序往往比快排还快。n 很大时 log 因子不可忽略,但瓶颈可能已经转移到内存带宽或磁盘读写。外部排序就是典型:数据装不进内存,一次磁盘读写抵得上几百万次比较,该优化的是 I/O。

最后是稳定性和可预测性。计数和基数排序可以做成稳定的,前提是写对展开顺序;快排和堆排不稳定;归并稳定但费内存。业务要求金额相同的订单保持创建时间顺序时,稳定排序就不是可选项。下界只回答最少比多少次,不回答相等元素怎么排。

当天能做的练习

  1. 给比较器加一个计数器,对一千个和一万个随机整数分别跑归并排序与内置排序,把实测比较次数和 ceil(log2(n!)) 写在一张纸上,算出各自高出下界百分之几。
  2. 用 4 个不同元素枚举全部 24 种排列,写一个只做比较的插入排序,手工记录每种输入走了多少次比较,找出最深的那个叶子,和 log2(24) 向上取整得到的 5 对照。
  3. 用循环累加 Math.log2(i) 计算 n 等于 100 万时的 log2(n!),再用斯特林公式的前两项算一次,把两个结果相减,解释差值的来源。
  4. 实现文中的计数排序,分别对一百万个 0 到 999 的整数和一百万个 0 到 99999999 的整数运行,记录耗时与峰值内存,说明第二组为什么不适合。
  5. 实现一个简单的桶排序,用均匀分布和指数分布各生成十万条数据,统计最大桶与最小桶的元素数量,观察桶排序在什么分布下开始退化。
环境说明:171.1 毫秒、3.9 毫秒、120319 次比较均来自本机 Node.js 24 的实际运行,计时前预热过一次。不同机器会得到不同数字,文中只用于比较量级和验证公式。

小结与下一篇

三句话收一下:排序的本质是把 n! 种排列区分开,每次比较只给一位信息,所以最坏情况至少要 log2(n!) 次比较;用斯特林公式算,一百万个元素的下界是一千八百四十九万次,这就是 n log n 的来历;这个下界只管只靠比较的排序,计数、桶、基数排序靠值域和额外空间跳出了这个模型。

但下界只是平均意义上的保证,并不妨碍某个算法在坏输入上退化。下一篇讲快排:固定选最后一个元素做 pivot,遇到已经有序的订单列表,比较次数变成平方级,递归深度等于 n,最后把调用栈撑爆。我们会用实测数据看它怎么涨到八百万次,再讲随机化、三数取中、内省排序和三路划分怎样补坑。