同事接了一个「按金额排序,取前 200 条订单」的报表需求。他花两天写了一个教科书式快排:取最后一个元素当枢轴,小的放左边、大的放右边,再递归处理两半。为了证明没白写,他造了 10 万个随机对象压测,结果比一行 Array.prototype.sort 还快一点,代码顺利合入。

上线第二天,报表接口开始超时。同一份数据本地十几毫秒,线上跑了十几秒。抓下入参才发现,导出的订单一开始就按创建时间排好,金额也大致递增。随机压测恰好绕开了这份代码最怕的输入。另一条链路还偶发一条报错,大意是比较器不符合一致性要求,但谁也复现不出来。

这篇回答三个实际问题:内置排序在真实数据上为什么经常赢,它到底做了什么,以及什么情况下该换成更专用的算法。文中毫秒数都来自本机 Node.js 24 的实际运行。

现场:随机数据赢了,报表却慢了一万多倍

枢轴(pivot)就是每一轮划分时选中的参照元素,比它小的去左边,比它大的去右边。末元素枢轴写法省事,但有个前提:输入要足够乱。如果输入已经有序,每一轮的最后一个元素恰好是当前范围的最大值,划分后左边剩 n 减 1 个,右边为空。下一轮还是同样的局面,一次只排除一个元素。

总比较次数于是变成 n 加 n 减 1 一直加到 1,约等于 n 的平方除以二。数据量翻一倍,时间大约翻四倍。10 万个元素约 50 亿次比较,本机要十几秒。代码没有死循环,也没有内存泄漏,它只是把有序数据当成了最坏情况。

末元素枢轴遇到有序输入时会发生什么
第一轮:枢轴是最大值,右侧为空
左侧剩 n 减 1 个,顺序仍然保持
下一轮:枢轴还是最大值,继续只切一个
比较次数累加成平方级,耗时失控

把递归改成先处理较短的一侧,确实能压低调用栈深度,避免栈溢出。本机这份代码就是这么写的,所以它能跑完,只是慢。栈没爆不等于问题解决,时间照样平方级。很多事故在本地能跑通,于是被误判成只是有点慢。

三组实测:赢在随机,输在有序

我用同一批 10 万个对象跑了三组数据。每组正式计时前先预热两轮,再跑 4 到 6 轮取平均;对象只有 id 和 score 两个字段,比较器是 (a, b) => a.score - b.score。手写版本用 Lomuto 划分、末元素枢轴,也就是事故里的写法。

输入Array.sort(TimSort)手写快排(末元素枢轴)差距
10 万个随机对象平均 20.5 毫秒平均 13.1 毫秒手写反而快约 1.6 倍
10 万个已有序对象平均 1.1 毫秒四轮 15 秒上下,平均 21.6 秒内置快一万多倍
10 万个近乎有序对象平均 2.2 毫秒四轮平均 17.4 秒内置快数千倍

第一行值得停一下:纯随机数据上,手写快排确实更快。它只做比较和交换,循环很紧;TimSort 要做 run 识别、维护合并栈、申请临时数组,通用比较器的调用次数也更多。第二行才是事故的真相:同样 10 万个对象,内置 1.1 毫秒,手写 15 秒左右,四轮里还有一轮抖到 41 秒。第三行的「近乎有序」只打乱了约千分之一的相邻元素,手写版本仍是 17 秒。

随机数组最容易造,也最容易骗人,它恰好抹掉了「利用已有顺序」的价值。真实数据往往有时间戳、自增编号、分页顺序,业务上不觉得有序,对排序算法却已经高度有序。

这些数字是本机一次测量的量级参考,不是基准测试结论。JIT、垃圾回收和机器负载都会让单轮结果波动,文中取多轮平均,并写明了「有序」和「近乎有序」的构造方式。

TimSort:先找现成的顺序,再补长,再合并

TimSort 是很多语言对对象数组的默认排序,Python、Java 和 V8 的 Array.prototype.sort 都能看到它的影子。它的核心想法很朴素:真实数据里往往已经有成段的顺序,先把这些段找出来,不要从零开始两两比较。

第一个概念是 run,中文叫天然有序段。从数组开头扫,连续升序元素算一个 run;连续严格降序也算一个,扫描到下降结束时原地反转成升序。这里必须严格降序,相等元素不能算进下降段,否则反转会打乱同分记录的顺序,稳定性就没了。

TimSort 的四步
扫描输入,切出天然有序的 run
run 太短就用插入排序补到 minrun
把相邻 run 按栈规则合并
一边连续占优时用 galloping 跳跃

第二个概念是 minrun,允许的最小段长。run 太短,合并时起不到「块」的作用,反而增加合并次数,所以用二分插入排序把短段补到 minrun 左右。插入排序在短数组上常数很小,比继续切分再合并划算。不同实现的阈值略有差异,常见取值在 32 到 64 之间;本机 V8 的具体常量我没有逐行确认。

第三个概念是合并规则。TimSort 把 run 压进一个栈,设栈顶往下三段的长度是 X、Y、Z,要求 X 大于 Y 加 Z,且 Y 大于 Z,不满足就先合并相邻的较短两段。这样各段长度大致按比例增长,避免「一个大段反复和很多小段合并」的浪费。第四是 galloping,中文常译作「疾驰模式」:合并时若一个 run 的元素连续多次胜出,就用二分查找直接定位插入位置,再整块复制,不改变渐进复杂度,只压低常数。

拼起来看,代价模型就清楚了。最好情况整份输入只有一个 run,扫一遍结束,接近线性;最坏仍有 O(n log n) 的比较次数保证,不会退化成平方级;代价是需要一块和输入等长的临时空间。稳定、能利用已有顺序、最坏有保证,这三点才是它成为默认实现的理由,而不是它比别人快多少。

稳定性与比较器:结果乱掉的两个来源

稳定性指键相等的记录排序后保持原来的相对顺序。比如两条订单金额相同,原来 A 在 B 前面,排完还应该是 A 在前。

内置 TimSort

稳定,同分记录保持原顺序;最坏 O(n log n);近乎有序接近 O(n);需要 O(n) 临时空间。

教科书快排

不稳定,同分记录会被打乱;平均 O(n log n),已有序退化 O(n²);原地排序。

本机用 10 万个 score 只有 1000 种取值的对象验证,Array.sort 排完后同分记录的 id 严格递增。最小例子更直观:四条 score 都等于 5 的记录,原始顺序 0、1、2、3,手写快排排成 3、0、1、2,内置仍是 0、1、2、3。四条的键完全相等,任何按 score 升序的断言都会通过,但业务看到的顺序已经变了。

第二个来源是比较器,也就是传给 sort 的函数:返回负数表示第一个在前,正数表示第二个在前,0 表示相等。它必须满足三条:自反,和自己比返回 0;反对称,a 小于 b 则 b 必须大于 a;传递,a 小于 b 且 b 小于 c,则 a 小于 c。

最容易破的是传递。下面的比较器是人为构造的:a 小于 b,b 小于 c,但 a 大于 c,形成闭环。它对每一对元素都有明确答案,却不存在任何一种顺序能让所有两两关系同时成立。

const cmp = (x, y) => {
  const pair = x.k + y.k;
  if (pair === "ab") return -1;   // a 小于 b
  if (pair === "ba") return 1;
  if (pair === "bc") return -1;   // b 小于 c
  if (pair === "cb") return 1;
  if (pair === "ac") return 1;    // a 大于 c,闭环形成
  if (pair === "ca") return -1;
  return 0;
};

本机拿 3 万个对象、只用 a、b、c 三种键跑这个比较器,每次先打乱再排,连续四次。四次输出开头分别是清一色 b、清一色 a、清一色 b、一串 a 后接 b,没有一次相同。更迷惑的是,逐对检查相邻元素,逆序对都是 0,看起来局部完全有序。闭环允许三种互相矛盾的整块顺序,任一种都能通过相邻检查,落点取决于输入排列。

这就是偶尔报比较器不一致的根源。同样的问题在 Java 的 TimSort 里会抛出违反通用契约的报错(未在本机实测)。JavaScript 这一侧,本机 Node.js 24.21.0、V8 13.6.233.17-node.53 没有抛异常,只安静地给出不同顺序。comparator does not conform to a consistent ordering 这类提示在不同引擎上行为不统一,本机没有复现,标为待确认;但结果未定义是确定的。

不要用布尔值当比较结果。布尔会转成 1 和 0,永远没有负数。本机用 (a, b) => a.id > b.id 排 10 万个对象,输出前十个是 715、773、504、640 这样的乱序,既不报错也不正确。字符串相减得到 NaN,规范把 NaN 当成 0,效果接近什么都不排,同样不报错。

什么时候不该用内置排序

内置排序是默认答案,但前提是用比较决定顺序,每次至少一次函数调用,下限是 O(n log n)。数据带额外结构时,绕开比较往往快一个量级。

第一种是值域很小。年龄 0 到 120,分数 0 到 100,订单状态只有几种,可以用计数排序(counting sort):开一个和值域一样大的数组当桶,扫一遍统计次数,再按桶的顺序倒出来。时间是 O(n 加 k),k 是值域大小。代价是 k 不能太大,否则空桶浪费内存;值域几百万而数据几千条时反而不划算。

第二种是数据已经分桶或分块。订单按城市分到不同文件,每个文件内部也有序,就不必倒在一起重排,直接多路归并。归并把几个有序序列合成一个,每次只比较当前头部。按高位分桶再对桶内排序的基数排序(radix sort),也是利用位这个结构绕开两两比较。

第三种是只需要前 k 个。报表只要金额最高的 200 条,没必要把 10 万条全排。维护大小为 k 的小顶堆,扫描数据,堆满后只和堆顶比较,更大就替换下沉,总成本 O(n log k)。另一种是快速选择(quickselect),借用快排的划分,每轮只往包含第 k 名的那一半递归,平均 O(n);它不稳定,不适合并发写入。

第四种是数据放不进内存。几百 GB 的日志只能外部归并:分块读进内存,每块排好写回临时文件,再多路归并,每次只保留每个文件的一小段。这时讨论快排还是 TimSort 没有意义,瓶颈在磁盘读写和归并路数。

还有两个工程取舍,和算法无关但常决定实际耗时。排序键计算贵时,别在比较器里每次重算,先把键存下来,排完再拆回去,这叫「先装饰再排序再还原」。中文或带变音符号的字符串排序,用 Intl.Collator,实例建在排序循环之外;每次比较都新建实例,开销比排序本身还大。

现象、真实原因与第一步排查

下面这些症状在排序问题里很常见。看到类似现象,先按最后一列做最小检查,不要一上来就怀疑数据源或重写排序。

现象真实原因第一步查什么
随机压测正常,上线后慢十几秒输入近乎有序,末元素枢轴每轮只切一个,退化为平方级枢轴怎么选,输入是否已有顺序
报比较器不符合一致性,或顺序莫名比较器不满足传递或反对称,排序结果未定义取 a、b、c,打印三次比较的符号
同一批数据排两次结果不同比较器用了随机数、当前时间或外部状态比较器是否是纯函数,只依赖两个入参
同分记录的顺序变了用了不稳定排序,或对相等元素返回非 0排序是否稳定,相等时是否明确返回 0
[10, 2, 1].sort() 得到 1、10、2没传比较器,默认转成字符串按字典序比较数字数组是否漏了比较函数
比较器返回 true 或 false布尔转成 1 和 0,永远没有负数比较器返回值是否为数字
字符串用相减比较,排序几乎不动相减得到 NaN,规范把 NaN 当成 0是否改用 localeCompare 或显式大小判断
排序慢,垃圾回收频繁比较器每次新建对象、正则或排序器昂贵对象是否提到循环外,或先算好排序键
排完后 undefined 都跑到末尾数组有空洞或 undefined,内置实现放最后排序前是否该过滤或补齐空值

前两行最容易误判。第一行像机器性能差,实际是数据形状和本地测试不同;第二行像引擎有 bug,实际是比较器没有定义合法顺序。第三、第四行常被归咎于排序不稳定,但有时只是比较器在相等时返回 1 或 -1。

边界与代价:内置排序也不是免费的

第一项代价是空间。合并两个 run 需要临时缓冲区,最坏和输入等长,所以空间复杂度是 O(n),不是原地排序。10 万个对象多一份引用数组还好,到了千万级,这部分内存和垃圾回收压力就要算进预算。

第二项是比较器的调用成本。每次比较都是一次函数调用,10 万个元素约要一两百万次比较,每次都有参数传递和返回值检查。对象字段访问比数字比较贵,跨模块调用还可能失去内联优化。这解释了排数字比排对象快、排字符串又比排数字慢。

第三项是行为差异。内置排序原地改数组,要保留原顺序得先复制或用 toSorted。数组里的空洞和 undefined 会被统一放到末尾,数据不干净时很显眼。数字数组不传比较器会按字符串比较,[10, 2, 1] 排成 [1, 10, 2];类型化数组的 sort 默认按数值升序,同样写法在普通数组和 Float64Array 上结果不同,本机已验证。

第四项是阻塞。排序是同步的,几十万条数据在浏览器主线程上排会卡住页面,在服务端则占满一个事件循环时间片。数据量再大,就不是换算法能解决的,要么分片,要么放工作线程,要么只取前 k 个。

选择顺序比较清楚:默认用内置排序,因为最坏有保证、稳定、对真实数据友好;只有数据带有它用不上的结构,或内存、阻塞成为硬约束时,才考虑专用算法。手写排序也可以,但要有明确理由,并用生产形状的数据验证过。

当天能做的练习

  1. 造三组 10 万个对象:随机、完全有序、只打乱千分之一。每组预热两轮后各跑五轮,记录 Array.sort 与末元素枢轴快排的耗时,写一句话解释随机组和有序组的结论为什么相反。
  2. 把枢轴换成随机选取和三数取中,重跑有序用例,观察退化是否消失。再故意去掉「先递归较短一侧」的写法,用 10 万条有序数据触发一次栈溢出,记录报错信息。
  3. 写一个 a 小于 b、b 小于 c、a 大于 c 的比较器,用 3000 个对象跑 sort,每次先打乱再排,连续五次记录输出前 30 个元素。统计相邻逆序对,确认本机是否抛异常。
  4. 准备 1000 条 score 只有五种取值的记录,分别用内置排序和手写快排,检查同分记录的原始顺序是否保留。再实现「先按城市、再按金额」的两趟排序,说明第二趟为什么必须稳定。
  5. 用同一份 10 万条数据取金额最高的 200 条,分别实现全排序后截断、大小为 200 的小顶堆、快速选择,比较耗时和结果是否一致,并说明数据量继续增大时各自的表现。
环境说明:本文耗时与排序行为均在本机 Node.js 24.21.0(V8 13.6.233.17-node.53)实际运行,未做跨浏览器或跨语言对照。不同引擎的报错文案、V8 的 minrun 常量属于待确认项,不应直接当成结论使用。

小结与组内回望

三句话收一下:内置排序的优势不在单次比较更快,而在先找有序段、补长短段、按规则合并,最坏仍守住 O(n log n);稳定性让同分记录的顺序可解释,比较器破坏自反、反对称、传递中的任一条,结果就未定义;只有数据带额外结构时,计数排序、桶排序、堆选择、外部归并才值得取代它。

回望排序这一组,前面几篇拆比较、交换、划分、合并这些零件,也讨论过稳定性为什么会丢。这一篇把它们装回工程现场:一段在随机数据上更快的代码,可能在真实数据上慢一万多倍;一个看起来对每对元素都有答案的比较器,可能根本定义不出全局顺序。判断排序问题,先问数据长什么样,再问比较器是否合法,最后才问算法本身。

如果只带走一个动作,那就是写排序逻辑之前,先把真实数据的前一万条打印出来,看它是不是已经有序、有没有大量同分、比较键是否干净。这花不了几分钟,却能避开这篇里几乎所有的坑。