快速排序为什么平均 O(n log n)、最坏 O(n²)

「快速排序平均 O(n log n)，最坏 O(n²)」几乎每本书都会写，但这两个结论从哪儿来，常常一笔带过。这篇只盯住一个量——元素之间的比较次数——把最好、最坏、平均三种情况分别算出来。文中每个数字都来自本站的快速排序演示，点开对应链接，变量表里的「比较次数」一栏会和正文一致。

先定下要数的东西

演示里的快速排序这样划分：取区间最后一个数当基准，从左到右扫一遍，把比基准小的数依次换到左边，最后把基准放到它们后面。一个长度为 m 的区间，基准要和另外 m − 1 个数各比一次，不多也不少。

所以整次排序的比较次数，就是每一次划分时区间长度减 1，全部加起来。区间长度怎样变化，完全取决于基准每次落在哪里。

最好情况：基准每次都落在正中间

如果基准恰好是区间的中位数，一个长度为 n 的区间会被分成两个长度约为 n/2 的区间。以 15 个数为例：

层	这一层的区间	每个区间比较	这一层合计
0	1 个长度 15	14	14
1	2 个长度 7	6	12
2	4 个长度 3	2	8
3	8 个长度 1	0	0

合计 14 + 12 + 8 = 34 次。每一层的比较总数都不超过 n，而区间每下一层就减半，一共只有大约 log₂n 层，于是总数不超过 n·log₂n 的量级，这就是 O(n log n)。

要让「取最后一个数当基准」的写法每次都取到中位数，输入得专门构造。本站算出的一组是 1,3,2,6,5,7,4,12,9,11,10,14,13,15,8，用这组输入打开演示，走到最后一步，比较次数正好是 34，最深递归 3 层。

最坏情况：基准每次都落在一端

把 1 到 16 按从小到大的顺序输进去。第一次划分，基准是 16，它比其他 15 个数都大，扫完之后一个数都没挪，基准留在最右边：左边剩 15 个数，右边是空的。下一次基准是 15，左边剩 14 个……每次只「消掉」一个数。

比较次数 = 15 + 14 + 13 + … + 1 = 16 × 15 / 2 = 120

一般地，n 个数就是 n(n − 1)/2 次，量级是 n²。用 1 到 16 的有序输入打开演示，结束时比较次数是 120，最深递归 15 层。完全逆序的 16 个数、16 个相同的数，在演示里同样是 120 次：前者的基准交替落在区间的最小值和最大值上，后者因为划分用的是「严格小于」，相等的数全都留在基准右边。

讽刺的是，「已经排好序」这种看起来最省事的输入，恰恰是这种写法的最坏情况。

平均情况：换个角度数

一层一层地数平均值很麻烦，因为每层的区间长度都是随机的。换一个角度：不按「划分」数，而按「哪两个数会被比较」数。

把 n 个数按大小排好，记作第 1 小、第 2 小……第 n 小。任取第 i 小和第 j 小（i < j），问：它们在整个排序过程中会不会被比较？

两个数之间只有一种比较方式：其中一个当基准时，另一个在同一个区间里。
看大小介于它们之间（含两端）的这 j − i + 1 个数。只要其中某个数当了基准，而它既不是第 i 小也不是第 j 小，那么第 i 小会被分到它左边、第 j 小会被分到右边，两者从此不在同一区间，再也不会相遇。
反过来，如果这 j − i + 1 个数里第一个被选作基准的恰好是第 i 小或第 j 小，它们就会被比较一次（而且只有这一次）。

当输入顺序是随机的，这 j − i + 1 个数里谁先被选作基准是等可能的，所以两者被比较的概率是 2/(j − i + 1)。把所有数对加起来就是比较次数的期望：

E[比较次数] = Σ(i<j) 2 / (j − i + 1) 令 d = j − i，间距为 d 的数对有 n − d 个： = Σ(d=1..n−1) (n − d) · 2 / (d + 1) 令 k = d + 1： = Σ(k=2..n) 2(n + 1 − k) / k = 2(n + 1)(Hₙ − 1) − 2(n − 1) = 2(n + 1)Hₙ − 4n

这里 Hₙ = 1 + 1/2 + … + 1/n，约等于 ln n。于是平均比较次数约为 2n ln n，换成以 2 为底的对数是 约 1.39 · n · log₂n，量级 O(n log n)。n 足够大时，它只比最好情况多出约四成；n 很小时差距会大一些（下表 15、16 个数的实测约多五成）。

用演示引擎核对这个公式

取 n = 16，公式给出 2 × 17 × H₁₆ − 64 ≈ 50.94。本站用固定种子生成 5,000 个 1 到 16 的随机排列，逐个交给演示引擎排序，比较次数的平均值是 50.89，和公式相差不到 0.1。这个核对写进了自动测试，每次构建都会重跑。

输入	n	比较次数	最深递归	对照
专门构造的最好输入	15	34	3	每层 ≤ n，共约 log₂n 层
随机排列（5,000 个的平均）	16	50.89	6.02	公式 2(n+1)Hₙ − 4n ≈ 50.94
从小到大有序	16	120	15	n(n − 1)/2 = 120
从大到小逆序	16	120	15	同上
16 个相同的数	16	120	15	同上（严格小于划分）

空间：看递归有多深

快速排序在原数组里交换，不需要额外的数组，但每层递归都要占一格调用栈。最好情况深度约 log₂n（15 个数是 3 层），最坏情况是 n − 1 层（16 个有序数是 15 层），随机输入平均在 6 层左右。所以额外空间通常写作「平均 O(log n)，最坏 O(n)」。

实际使用时怎样避开最坏情况

随机选基准：从区间里随机挑一个数和最后一个数交换后再划分。这样不管输入长什么样，上面「随机顺序」的推导都成立，期望比较次数仍是 2(n+1)Hₙ − 4n。
三数取中：取区间首、中、尾三个数的中位数当基准，对已经有序或接近有序的输入特别有效。
三路划分：把区间分成「小于、等于、大于」三段，等于基准的数不再参与后续递归，大量重复值时不会退化。
先递归短的一边：短的一边递归处理，长的一边改成循环，可以把调用栈深度压在 O(log n) 以内。
小区间改用插入排序：区间只剩十几个数时，插入排序常数更小。

小结

快速排序的比较次数等于「每次划分的区间长度减 1」之和。基准落在中间，区间对半缩小，约 log₂n 层、每层不超过 n 次，是 O(n log n)；基准总在一端，每层只少一个数，加起来是 n(n − 1)/2，是 O(n²)；输入顺序随机时，任意两个数被比较的概率是 2/(j − i + 1)，求和得到约 1.39 n log₂n。三个结论都能在演示台上用具体输入看到。