quicksort · partition

quicksort：分区与 pivot

quicksort 的骨架只有三步：挑一个元素当分界，把区间重排成「不大于它」与「不小于它」两段，再对两段各自递归。实现之间的差异全部落在中间那一步，而它也是唯一会写坏的一步：指针的开闭、相等元素归哪一边、分界最后停在哪里，写错的后果通常不是慢一点，而是死循环或越界读。

本页先给出分区的契约与两种经典写法，再看分界的选法如何决定递归树的形状，然后处理重复键这个单独的难题，最后是工业实现用来堵住最坏情形的那道闸。归并方向上的对偶做法见自适应归并排序。

1 · 分区的契约

partition 的契约是这样一句话：给定数组区间 $[lo, hi]$ 与其中一个元素 $p$ ，把区间重排，使得存在一个分界下标 $q$ ，左段 $[lo, q]$ 的每个元素都不大于 $p$ ，右段 $[q+1, hi]$ 的每个元素都不小于 $p$ 。被选中的那个 $p$ 叫 pivot。

一次 partition 扫过区间一遍，代价 $\Theta(m)$ ， $m$ 是段长。递归树同一层的段互不重叠，每层加起来仍是 $O(n)$ ，所以总代价等于 $O(n)$ 乘树高。两段等长时树高 $\Theta(\log n)$ ；每次只切下一个元素时树高 $\Theta(n)$ ， $O(n^2)$ 由此而来。这条递推的一般形式见分治与主定理。

契约里有两处刻意的松弛，后面两节都会用到：等于 $p$ 的元素落在哪一段不作规定；分界 $q$ 也不必是 $p$ 自己所在的位置。Lomuto 的写法把 $q$ 钉死成 pivot 的最终落点，Hoare 的写法不给这个保证。

2 · Lomuto 与 Hoare 的指针边界

Lomuto partition 取区间末位当 pivot，用下标 $i$ 标记「已确认不大于 pivot」那一段的右端，下标 $j$ 从左向右扫； $a[j] \le p$ 就把它换进左段。扫完再把 pivot 换到 $i+1$ ，那一格就此定型。比较次数恒为 $m-1$ ，实现只有五行。

Hoare partition 从两端相向走： $i$ 向右直到撞见不小于 pivot 的元素， $j$ 向左直到撞见不大于 pivot 的元素，两者尚未交错就交换。它的交换次数明显更少，在重复键上给出的分割也比 Lomuto 均衡得多。

代价是边界更难写对。两个内层循环必须用严格的 $<$ 与 $>$ ：

警示 · 把两处判定放宽成 <= 与 >= 会让指针冲出区间。放宽后两个指针都会越过与 pivot 相等的元素：12 个全等元素的输入上实测越界两次、返回的分界是 $lo-1$ ，左段为空而右段仍是整个区间，递归再也收缩不下去。教科书举的例子通常止于全等数组，但 12 个元素的已升序输入同样翻车， $j$ 一路退到 $lo-1$ 、越界一次，后果相同。C 实现里这两处越界是真的读到了数组之外，JS 里读到 undefined、比较恒为假才侥幸停住。

严格判定的另一面是指针会停在与 pivot 相等的元素上，把它们两两互换。这些交换对结果毫无贡献，却让重复键的分割落在中点附近，代价与收益的账在 §4 结清。

还有一处约定换不得：返回 $j$ 的这种写法要求 pivot 取自 $a[lo]$ 。改取 $a[hi]$ 时 $j$ 可能等于 $hi$ ，于是右段为空、左段等于原区间，递归照样不收缩。

图 2-1 · 三种分区写法的单步执行。柱高是值，上方色签是指针，底色是当前已确认的归属。可切换方案与输入，越界次数在读数条右端。

3 · pivot 的选法与递归深度

末位取 pivot 的写法在已排好序的输入上退化得最彻底，每次分区只切下一个元素。 $n = 24$ 的升序输入实测 276 次比较（即 $n(n-1)/2$ ）、递归深度 24； $n = 1000$ 时是 499500 次比较、深度 1000。深度等于 $n$ 意味着真实实现会栈溢出，而不只是变慢一档。

median of three 取 $a[lo]$ 、 $a[mid]$ 、 $a[hi]$ 三者里居中的那个。同一份 $n = 24$ 的升序输入上，它把比较次数压到 115、深度压到 5：有序数组的这三个位置里，中间那个就是全段的 median。

注 · median of three 在随机输入上并不省比较。原先预期它对随机排列也有可观收益，实测把这个预期推翻了： $n = 1000$ 的随机排列下，200 组种子里末位 pivot 平均 11055.0 次比较、median of three 11023.5 次；换成 800 组则是 11001.2 与 11042.3。差距始终在 0.4% 以内，连符号都随样本量翻转。它每次分区自己要多花 3 次比较，把省下的又还了回去。被明确改善的只有递归深度，两个样本量下都是 22.1 对 16.8。改的是正文的说法，不是实现。

随机取 pivot 换掉的是保证的来源：期望 $O(n \log n)$ 对每一份输入都成立，运气由算法自己的随机数决定，不再由输入的形状决定。对任何确定性的 pivot 规则都存在使其退化的输入，McIlroy 构造的对抗式比较器甚至能在与被测程序交互的过程中现场把输入拧成最坏情形 [3]。

本系列的随机化走 core/rng.ts 里带种子的 mulberry32。用 Math.random 会让同一页两次刷新走出不同的帧序列，正文引用的数字也就无从核对。

图 3-1 · 整趟 quicksort 的分区级回放。上方是数组，下方每一行是一个递归层、横向为下标。可换输入与 pivot 规则，也可打开 introsort 兜底，观察深度被截断在哪一层。

4 · 重复键与三路切分

Lomuto 把所有等于 pivot 的元素都收进左段。键的种类一少，这条规则就成了灾难：600 个元素只取 3 种值时，实测递归深度 210、分区 597 次、比较 63217 次。Hoare 在同一份输入上深度只有 14，相等元素让两个指针一起停下并交换，分割因此靠近中点。

three-way partitioning（Dijkstra 的荷兰国旗问题 [5]）把区间切成三段：小于、等于、大于。等于 pivot 的那一段一次到位，此后不再进入任何递归。同一份 600 个元素的输入上实测深度 3、分区 3 次、比较 1788 次。

三种方案的比较次数不可直接横比。core/quicksort.ts 对 Lomuto 计每次分区固定的 $m-1$ 次，对 Hoare 计两个指针每次停下时的那一次，对三路计落在每个元素身上的 1 到 2 次。口径既然不同，跨方案有意义的就只剩递归深度与分区次数；同一方案内跨输入的比较仍然成立。

三路分区的总代价随键分布的熵走，键的种类越少越省。Bentley 与 Sedgewick 给出了这个意义上的最优性论证 [2]，它与自适应归并排序里 Powersort 的熵界同源：两处都在说「代价正比于输入实际携带的信息量」。

图 4-1 · 三路分区的单步执行，以及三种方案在 600 个元素上的整趟代价。三个指针把区间切成四块，中段一旦定下就不再移动。

5 · 递归深度阈值与兜底

introsort 给递归深度设一个阈值 $2\lfloor \log_2 n \rfloor$ ，越过就把当前区间整个交给 heapsort [4]。heapsort 最坏也是 $O(n \log n)$ 且原地，补上的正是 quicksort 唯一的短板；而阈值在正常输入上碰不到，quicksort 的常数得以保留。堆本身的机制见 binary heap。

$n = 24$ 时阈值是 8。末位 pivot 的升序输入原本要 276 次比较、深度 24；开启兜底后实测 235 次比较、深度 8，其中一次落到 heapsort。兜底的用处在尾部风险：把 $O(n^2)$ 削到 $O(n \log n)$ ，正常输入上的常数一分不动。

建议 · 标准库的取舍并不一致。C++ 的 std::sort 是 introsort。V8 的 Array.prototype.sort 走 TimSort，短数组上根本不归并：拿两段完美交错的升序 run 作输入，node v26.8.1 的比较器调用次数在 $n = 63$ 时是 213 次， $n = 64$ 时降到 126 次，归并路径在 64 这一档打开；同样在 $n = 63$ ，一个随机排列要 292 次，与二分插入排序的 292 次分毫不差。已升序或已降序的输入无论多长都只花 $n-1$ 次（核对于 2026-08）。

6 · 参考文献

Hoare, C. A. R. (1961). Algorithm 64: Quicksort. Communications of the ACM, 4(7), 321.
Bentley, J. L., & McIlroy, M. D. (1993). Engineering a sort function. Software: Practice and Experience, 23(11), 1249–1265.
McIlroy, M. D. (1999). A killer adversary for quicksort. Software: Practice and Experience, 29(4), 341–344.
Musser, D. R. (1997). Introspective sorting and selection algorithms. Software: Practice and Experience, 27(8), 983–993.
Dijkstra, E. W. (1976). A Discipline of Programming. Prentice-Hall, 111–116.