去年做一张订单报表,接口返回的数据本来就按创建时间升序排好了,前端为了保险又调用了一次排序。数据量到一万条时页面直接白屏,控制台只有一行 RangeError: Maximum call stack size exceeded。更让人想不通的是,同样一万条数据,打乱顺序再排就一点问题没有。

问题出在排序实现上:最普通的快速排序,每次都拿区间的最后一个元素当 pivot。已有序的数组里,最后一个元素恰好是最大值,划分后其余元素全落左边,右边为空。每加一层数据就多一层递归,一万条要递归一万层,调用栈先撑不住;就算栈够深,比较次数也已涨到平方级。

这篇先看退化的具体数字,再解释比较次数和递归深度为什么变成 n 的平方与 n,然后依次讲随机化、三数取中、小区间插排、内省排序和三路划分。它们不是五个孤立的技巧,而是在不同层面补同一个洞:pivot 选得差、递归太深、重复键太多。

现场:一万条有序数据把栈撑爆

先看最朴素的实现。pivot(枢轴元素)是划分时当标尺的元素,比它小的放左边,大的放右边;递归深度是函数调用自己的层数,每进一层占一段栈。下面用最后一个元素做 pivot,划分是最常见的 Lomuto 方案:指针 i 记录「小于 pivot 的区域」右边界,遍历一遍把小元素换到前面。

function quickSortLast(a, lo = 0, hi = a.length - 1) {
  if (lo >= hi) return a;
  const pivot = a[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (a[j] < pivot) {
      [a[i], a[j]] = [a[j], a[i]];
      i++;
    }
  }
  [a[i], a[hi]] = [a[hi], a[i]];
  quickSortLast(a, lo, i - 1);
  quickSortLast(a, i + 1, hi);
  return a;
}

本机用 Node.js 24 跑了三组规模,分别输入升序数组和随机数组,统计比较次数与最大递归深度。深度从根调用算 0 层,一千个元素最深是 999。

n输入比较次数最大递归深度
1000已升序499500999
1000随机1085121
2000已升序19990001999
2000随机2547925
4000已升序79980003999
4000随机5179323
10000已升序未跑完,先抛栈溢出超出调用栈

表里最刺眼的是两列对比:同样四千个元素,有序输入比较七百九十九万八千次,随机输入只比较五万一千七百九十三次,差一百五十多倍;深度一边三千九百九十九,一边二十三。有序输入的增长也很清楚:一千是四十九万九千五百,两千是一百九十九万九千,四千是七百九十九万八千,每翻一倍,比较次数翻四倍。这就是平方级,不是 n log n 多了个常数。

固定末尾 pivot 在有序列上的划分
取最后一个元素当 pivot,它恰好是最大值
每个元素都比 pivot 小,全部换到左边
右半边为空,只递归左半边
下一层重复同样的事,深度等于 n

所以第一个结论是:快排的「平均 n log n」不是无条件成立的。它的成本取决于 pivot 能不能把数组切成两半,而固定取末尾的写法,把「切得平均」完全交给了输入顺序。输入越接近有序,越容易切出「一边零个、另一边 n 减一个」的最坏情况。

为什么有序输入最坏

把划分写成递推式就清楚了。区间长度 n,pivot 是最大值,划分要比较除 pivot 外的 n 减 1 个元素,并把它们全放到左边。剩下要排长度 n 减 1 的区间,于是 T(n) 等于 T(n 减 1) 加 n 减 1,边界 T(1) 等于 0。展开就是 n 减 1 加到 1,等于 n 乘 n 减 1 再除以 2。

拿一千验证:一千乘九百九十九除以二,正好是 499500,和实测一致;两千是 1999000,四千是 7998000,也都对得上。这不是误差,而是最坏情况的精确公式。数据量到一百万时,公式给出约五万亿次比较,按每秒一亿次算要十几个小时。

递归深度也是同一个原因。每次划分只排掉一个元素,剩下 n 减 1 个继续,最长调用链有 n 层。每层调用都要保存参数、返回地址和局部变量,Node 24 的默认栈约一万层,所以一万条数据刚好越界。浏览器栈上限因引擎而异,但量级相近,前端遇到同样输入也会白屏。

除了升序,还有两种输入同样致命。完全逆序时最后一个元素是最小值,所有元素落到右边,左半边为空,仍然每次只排掉一个。全部元素相等时,Lomuto 方案里 a[j] < pivot 永远为假,i 停在开头,划分后左边为空、右边 n 减 1 个,退化得一模一样。本机对四千个全等元素实测,比较 7998000 次、深度 3999,和升序相同。

这三种输入在业务里都不罕见:订单按时间插入天然接近有序;导出日志按自增 id 排列也是有序;某个字段只有几个固定取值,重复键非常多。快排的坏输入不需要恶意构造,日常数据就能撞上。

换 pivot:随机化与三数取中

既然问题来自 pivot 总是最大值,最直接的修法就是别固定选末尾。随机化(randomized quicksort)指每次划分前在区间里随机挑一个元素,和末尾交换后当 pivot。这样 pivot 是最大值的概率只有 n 分之一,而且对任何固定输入都成立,包括别人特意构造的坏数据。代价是每次划分多一次随机数生成和一次交换。

本机对四千个已升序元素做随机 pivot,实测比较 54144 次、深度 27,和有序输入的 7998000 次、3999 层相比,已经回到正常范围。随机化把「输入顺序」和「算法行为」解耦:不管数据怎么排,pivot 的分布都差不多,切分也差不多平均。它换来的 n log n 是期望意义上的,代价是结果不可复现,测试要固定种子。

三数取中(median of three)是另一条路:取区间第一个、中间、最后一个元素,比较三次,把中位数换到末尾当 pivot。对已有序数组,首、中、尾正好是最小、中间、最大,中位数落在正中,划分几乎对半分。本机对四千个有序元素实测 46058 次比较、深度 11;对四千个逆序元素是 81858 次、深度 26。逆序稍差,但仍远离平方级。

三数取中的问题是对手能构造专门输入:算法固定看三个位置,就造一组数组让每次取到的都是偏大或偏小的值,每层都切得很偏。这类输入不会随机出现,但只要服务允许用户控制数组顺序,就必须考虑。随机化没有这个弱点,因为对手不知道你这次挑哪个下标。

随机化 pivot

每次划分随机挑一个元素,坏输入概率降到 n 分之一,期望比较约 1.39 乘 n 乘 log2(n)。实现简单,对任何输入都稳。代价是随机数开销,结果不可复现,测试要固定种子。

三数取中

看首、中、尾三个元素取中位数,对有序和逆序都有效,本机四千有序元素只要 46058 次比较、深度 11。没有随机数开销,但固定规则可被构造输入针对。

工程上常见做法是把两者叠起来:先三数取中,必要时加一点随机扰动;或者九数取中,从更多位置抽样。取中位数要花几次比较,样本越大越稳,额外比较也越多。对绝大多数业务数据,三数取中够用;对允许外部控制顺序的接口,随机化更让人放心。

小区间改用插入排序

区间很小的时候,继续分治就不划算。三五个元素的区间,用快排要建栈、划分、递归,而插入排序(insertion sort)只要几个循环,常数极小,在几乎有序的小数组上很快。常见做法是设阈值,长度小于 8 到 16 时直接插入排序,不再递归。

这一步有三重收益。第一,省掉大量函数调用,小数组的递归开销常比比较本身还大。第二,减少递归层数,最底下几层数量最多,砍掉它们对栈深度和调用次数都有好处。第三,划分后的子区间往往接近有序,正好是插入排序的主场。

阈值不是越大越好。设成 32 或 64,插入排序的平方级成本开始显现;设成 4,又几乎没有收益。标准库多取 16 左右,但这个数字和语言、缓存都有关系,换环境要重测。稳妥的做法是拿真实数据跑 8、16、24 三档比较总耗时,而不是照抄常数。

还有一个细节:小区间用插入排序后,整个排序不再是纯快排,最坏情况分析要重做。插入排序只处理常数大小的区间,最坏仍由划分决定;但阈值设得很大时,平方级的插入排序会影响整体上界。所以内省排序要把阈值和堆排兜底一起考虑,而不是单独看某一段。

内省排序:深度超了就用堆排兜底

随机化和三数取中把坏输入的概率压得很低,但很低不是零。只要还存在深度为 n 的调用链,就还有栈溢出的可能。内省排序(introsort)给递归加预算:深度超过上限就不再快排,改用堆排序(heapsort)排完当前区间。堆排最坏 n log n,原地,不需要额外空间。

预算通常取 2 乘 floor(log2(n))。随机快排的深度大多在 log2(n) 的两倍附近波动,取两倍作上限,正常输入几乎不触发,坏输入一定会被拦住。本机一万个有序元素上限 26、实际深度 26,触发一次堆排兜底,总比较 503389;十万个有序元素上限 32、触发一次,总比较 6310888;十万个随机元素触发七次,总比较 2077142。

代码结构大致是这样:先算全局深度预算,递归时把深度传下去;区间小于阈值就插排,超过预算就堆排,否则正常划分。预算要用整个数组的 n 只算一次,不能每个子区间各算各的,否则深层小区间会重新获得预算,兜底永远不触发。

const limit = 2 * Math.floor(Math.log2(n));
function sortRange(lo, hi, depth) {
  if (hi - lo < 16) { insertionSort(lo, hi); return; }
  if (depth > limit) { heapSort(lo, hi); return; }
  const p = partition(lo, hi);
  sortRange(lo, p - 1, depth + 1);
  sortRange(p + 1, hi, depth + 1);
}

堆排兜底的代价是常数大、缓存不友好,只该出现在异常路径上,不能当主力。健康的实现里兜底次数应该很少;如果监控发现它频繁触发,说明 pivot 策略有问题,或者数据分布特殊,应该先查策略,而不是调大预算。调大预算只是让坏情况晚一点发生,没有解决切分不均。

顺带说一句标准库:C++ 的 std::sort 通常是内省排序,最坏 n log n;Java 对象排序和 V8 的 Array.sort 用 TimSort,基本有序时非常快。它们都不是裸快排,因为裸快排在真实数据上太容易翻车。自己实现时,要么用标准库,要么至少补齐随机化、小区间插排和深度兜底。

重复键:三路划分

前面说过,全部相等时 Lomuto 划分会退化成每次只排掉一个。真实数据里很少有全部相等,但只有几种取值很常见,比如订单状态只有四种,按状态排序时重复键占绝大多数。两路划分把小于 pivot 和不小于 pivot 分开,等于 pivot 的元素会反复参与后续划分,成本仍很高。

三路划分(three-way partition,也叫荷兰国旗划分)把区间分成小于、等于、大于 pivot 三段。一次划分就把等于 pivot 的元素放到最终位置,之后只递归两边。重复键越多省下越多;全等时一次划分就结束。

function quickSort3Way(a, lo = 0, hi = a.length - 1) {
  if (lo >= hi) return a;
  const pivot = a[lo];
  let lt = lo, i = lo + 1, gt = hi;
  while (i <= gt) {
    if (a[i] < pivot) {
      [a[lt], a[i]] = [a[i], a[lt]];
      lt++; i++;
    } else if (a[i] > pivot) {
      [a[i], a[gt]] = [a[gt], a[i]];
      gt--;
    } else {
      i++;
    }
  }
  quickSort3Way(a, lo, lt - 1);
  quickSort3Way(a, gt + 1, hi);
  return a;
}

本机对照:四千个全等元素,两路 Lomuto 比较 7998000 次、深度 3999,三路只 3999 次、深度 1;一万个元素、十种取值、随机打乱,两路 5029066 次、深度 1044,三路 39933 次、深度 5。差距不是常数级,而是从平方回到线性附近。

三路划分也不是免费的:取值几乎不重复时,每个元素可能多做一次比较,常数略高,划分逻辑也更复杂。但重复键多时,这点代价远小于收益。判断要不要用,先统计键的基数:几十种取值以内、数据量大,三路通常值得;几乎全不重复,两路加随机 pivot 就够了。

现象、原因与第一步排查

快排的问题常被说成「偶尔卡一下」或「数据量一大就崩」。先按表里的第一步定位,不要一上来就重写排序。

现象真实原因第一步查什么
已经有序的数据排序特别慢固定末尾 pivot,每次都切出空的右半边打印每次划分后左右区间的长度
报 Maximum call stack size exceeded递归深度等于 n,超过调用栈上限记录最大递归深度和 n 的关系
少量重复键时也退化成平方两路划分把所有等于 pivot 的元素推到一侧统计键的基数与相等元素比例
加了深度预算仍然很慢堆排兜底频繁触发,说明 pivot 策略本身有问题统计兜底次数与触发时的区间长度
平均很快但偶发几十秒坏输入命中了深分支,且没有兜底记录深度直方图与最坏单次耗时
测试结果无法复现随机 pivot 没固定种子,每次划分路径不同测试环境固定随机种子
小区间改用插排后整体变慢阈值设得太大,平方级插入排序吃掉收益用 8、16、24 三档实测对比
排序后相同键的顺序乱了快排本身不稳定,相等元素相对次序被打乱确认业务是否需要稳定,必要时加次序键

表里最容易误判的是第四行和第五行。兜底触发本身不是坏事,它是安全网;但一张表里触发几百次,说明 pivot 一直切偏,该换策略,而不是调大预算。第五行更隐蔽:平均耗时正常,只有 P99 变差,根因是一次坏输入把深度拉满。记录深度分布比只看平均耗时更有用。

边界与代价

快排的优势是原地和缓存友好:不用像归并那样开一块同量级的空间,划分时顺序扫描,实际通常比堆排快。代价是最坏仍是平方级,除非加了内省兜底;而且它不稳定,相等键的相对顺序会变。业务要求相同金额保持创建时间顺序时,要么改用归并,要么在比较键里加上创建时间。

递归实现还有栈的限制。预算取 2 乘 log2(n) 是常见值,太小会频繁触发堆排,太大又起不到保护作用。改成显式栈能避开调用栈,但代码复杂、常数略高,除非数据特别大或栈很小,一般不必这么做。

数据分布也决定选型。几乎有序时,TimSort 和插入排序接近线性,裸快排反而最差;重复键多时三路划分优势明显;顺序可被构造的外部输入,随机化加内省最稳。没有一种快排对所有场景都最优。

最后是并行和外部场景。多核可以把左右子区间分给不同线程,但划分本身串行,小数组并发开销大于收益。数据装不进内存时,快排的随机访问会让磁盘来回寻道,该用外部归并排序,下一篇会讲。快排的快建立在三个前提上:数据在内存、pivot 切得平均、深度可控。

当天能做的练习

  1. 把文中的 quickSortLast 原样敲进去,对 1000、2000、4000 个已升序元素运行,打印比较次数和最大深度,验证它们等于 n 乘 n 减 1 除以 2 和 n 减 1。
  2. 改成随机 pivot,用同一组有序数据再跑一次,记录比较次数和深度,并说明为什么结果不能复现;再固定随机种子跑三次,确认三次一致。
  3. 实现三数取中,对有序、逆序、全部相等三组四千元素各跑一次,把比较次数和深度记在表里,和随机 pivot 的结果对照。
  4. 给快排加一个深度预算,超过 2 乘 floor(log2(n)) 就改用堆排,对一万个有序元素运行,统计兜底触发次数和总比较次数。
  5. 实现三路划分,对四千个全部相等的元素和一万个只有十种取值的元素运行,和两路 Lomuto 版本的比较次数做对比。
环境说明:文中的比较次数与深度来自本机 Node.js 24 的实际运行,数据用固定种子生成。不同引擎的调用栈上限不同,抛栈溢出的具体阈值有差异,但「深度等于 n」这个结论与语言无关。

小结与下一篇

三句话收一下:固定末尾 pivot 遇到有序或全等输入,每次只排掉一个元素,比较次数是 n 乘 n 减 1 除以二,深度是 n;随机化和三数取中把切分拉回平均,小区间插排和深度兜底压住常数与栈风险,三路划分专治重复键;快排的原地和缓存友好值得保留,但最坏保证要靠内省排序。

下一篇转向另一个极端:数据多到内存装不下。快排再快也只能在内存里换元素,外部排序面对的却是磁盘,一次读写就抵得上几百万次比较。我们会讲外部归并排序怎样分块、排序、写回、多路合并,以及它为什么宁愿多读几遍磁盘,也要把随机访问换成顺序访问。