不知道你是面试被问懵了还是自己写快排时实测跑出过接近 O(n^2) 的时间反正“随机快排时间复杂度是 N 平方”这句话传得很广。正面回答理论上随机快排的最坏情况确实是 O(n^2)但随机化之后出现这种最坏情况的概率低到基本可以忽略它的期望时间复杂度稳定在 O(n log n)。问题在于很多人把“最坏”和“期望”混为一谈又在写代码时踩了随机挑选策略、重复元素处理这些坑结果跑出性能暴跌回头就信了“随机快排还是 N 平方”的鬼话。这篇文章我不想只背一遍算法导论推导而是把快排复杂度从直觉到数学、再到工程实现里的那些细节捋一遍。你会知道为什么随机化能救命也知道哪些情况下它确实救不了以及怎么写出一个真正的、工程可用的随机快排。1. 先从复杂度拆解开始快排的时间到底花在哪里1.1 划分的开销与递归结构快排的核心操作是 partition。给定一个数组和一个基准 pivot一趟划分会把比 pivot 小的元素放左边、比 pivot 大的放右边。这一趟做下来你至少要比较 n-1 个元素也就是说单次划分的时间是 O(n)。然后你递归去处理左边和右边两个子数组。整个算法消耗的时间等于每一层递归中所有划分的开销之和。这里的关键点在于不划分得匀不匀递归深度完全不一样。如果每趟划分都把数组分成差不多两半递归深度是 O(log n)每层总共 O(n)总时间就是 O(n log n)。如果每趟划分都只分出 1 个和 n-1 个元素递归深度变成 n每层还是 O(n)总时间就成了 O(12...n) 的叠加最终是 O(n^2)。我记得自己第一次手写完快排拿一个接近有序的数组测试跑了十万个元素就明显卡顿。当时还以为是电脑太破后来打印出每次递归的子区间才发现递归树已经退化成一条“倒链”。这就是快排复杂度最直观的真相复杂度不是由平均划分决定的而是由最差划分路径决定的。1.2 递归公式最好、最坏、平均用递归式表示会更清楚。最好情况是每次 pivot 都是中位数划分均匀T(n) 2T(n/2) O(n)解得 T(n) O(n log n)。最坏情况是每次 pivot 都是当前区间的最小或最大值T(n) T(n-1) T(0) O(n)解得 T(n) O(n^2)。“平均”情况在算法分析里有两种理解一是输入的平均分布也就是假设所有输入排列等概率出现二是随机选择 pivot 后的期望。传统快排分析会取所有可能的输入排列平均结论是平均时间复杂度 O(n log n)。但工程上没人真正依赖“输入均匀”——因为实际输入往往严重偏离均匀分布比如已经排好序的数据你拿固定策略选 pivot 选到的就永远是最大或最小值。随机快排的思路就绕开了对输入的假设不是赌输入分布而是用随机化把坏情况的分裂概率摊进去让算法的期望不再依赖输入的形式。这里说的“期望”是对随机数生成器取平均不是对输入取平均。这个区别很重要输入再恶意只要随机源够好它没法稳定地制造每次都选到最小值的场景。随机化的本质不是让最坏情况消失而是让最坏情况变成一个极小概率事件让算法面对任何固定输入都表现稳定。2. 随机化为什么能兜底期望 O(n log n) 的数学直觉2.1 最坏情况其实是一个概率事件固定选择策略的快排比如每次拿数组第一个元素做 pivot只要输入构造得当你必死。随机化之后呢假设 pivot 是均匀随机选的某次划分“非常不平衡比如选到了区间最大或最小值”的概率是 2/n。如果区间长度是 10000这个概率只有万分之一。但随着递归深入你可能会连续选到不合适的 pivot。比如数组长度 8 时选到最大值的概率是 1/4连续两层都选到边界值的概率是 1/16连续 k 层都选到边界值的概率是 (1/n)^k 之类的。真正需要担心的不是某一次划分不好而是坏划分在一整棵递归树上的累积。随机化让这种累积概率以超指数速度衰减。很多人会问如果运气真的差到极点随机化不照样是 O(n^2)对理论上就是。随机快排的最坏情况依然是 O(n^2)这与随机化不冲突。但实际工程里一个 2^32 规模的数组你能随机出连续 32 次都选到最大值的概率接近 1/2^4096这个概率比宇宙中某个指定原子突然消失还小得多。所以工程上从不担心这件事。2.2 期望复杂度的主要推导思路要有说服力地讲“随机快排期望 O(n log n)”最经典的方法是指示器随机变量法。定义一个随机变量 X_n表示长度为 n 的数组在随机快排中所需要的比较次数。关键观察是数组里的任意两个元素 a 和 b 在整个排序过程中最多被相互比较一次。为什么因为一次比较发生在 pivot 选择之后假设 x 是某次划分的 pivot那么任何元素和 pivot 进行过比较之后 x 不会再参与后续排序其他元素要么到左边要么到右边两个阵营之间不会再发生跨区间比较。也就是说任意一对元素要么从未比较要么只比较一次。我们用指示器 X_ij 表示第 i 小元素和第 j 小元素在排序过程中是否发生过比较那么总比较次数所有 X_ij 之和。要算期望就只需要知道第 i 小元素和第 j 小元素发生比较的概率。这里有一个巧妙的角度考虑这 j-i1 个元素组成的集合从第 i 到第 j 小的元素。在所有这些元素中如果选到它们的中间某个非端点的元素作为第一次被选中的 pivot那么第 i 小元素和第 j 小元素会被划分到两边以后永远不会互相比较。只有在这 j-i1 个元素中第 i 小或第 j 小的元素恰好是最早被选为 pivot 的那个它们才会发生比较。这两个候选在集合里被选中的概率各为 1/(j-i1)合计 2/(j-i1)。所以 E[X_ij] 2/(j-i1)。对全部下标对求和E[X] Σ_{ij} 2/(j-i1)。把 j-i 记为 d那么 d 从 1 到 n-1共有 n-d 对所以E[X] Σ_{d1}^{n-1} (n-d) × 2/(d1) ≤ 2n × Σ_{d1}^{n-1} 1/(d1)。右边的调合级数约等于 ln n于是期望复杂度 O(n log n)。这段推导在算法导论或各种讲义里都有但我建议你自己手推一遍因为只有推过才会真正明白那句“期望线性性”用在哪里以及为什么我们不需要管随机变量之间的相关性。2.3 直觉上的“为什么很少偏太多”除了严格的期望证明我还喜欢用“概率递归树”来给自己做一个直觉校验。快排在递归时每一步如果 pivot 的排名落在 25% 到 75% 之间我们就算一次“良好划分”。一次良好划分能保证后续两个子问题的规模都不超过原来的 3/4。一个均匀随机选择的 pivot落在中央 50% 区间的概率正好是 1/2。你可以把连续几次划分压缩成这样一个步骤以一个不超过 3/4 的分裂比率把问题规模缩小到原来的 3/4。平均需要尝试多少次随机 pivot 才能拿到一次良好划分几何分布期望是 2 次。于是问题的递归深度符合一个近似步骤每步把 n 变成 3n/4总的递归层级就是 log_{4/3}(n)。这一套思路虽然不够严谨但对现场估算复杂度很有用。真正写代码做性能预判时我就是用它来快速验证某个排序策略大概会退化到什么程度。3. 工程上的随机快排到底怎么写的3.1 别把“随机”写成找最大值很多人写随机快排自以为很懂void quickSort(vectorint a, int l, int r) { if (l r) return; int pivot a[l rand() % (r - l 1)]; while (i...); // 某个 partition quickSort(a, l, pos - 1); quickSort(a, pos 1, r); }问题在于pivot 是随机选的但你的 partition 实现可能并不支持“任意位置做 pivot”最后拼代码的时候出现明明 pivot 换到中间位置交换逻辑却写错导致划分结果反而偏向一端。我给人 review 代码时见过不少次随机 index 选了但 pivot 又赋值成 a[l]等于没随机或者随机 index 和数组长度写错导致越界。这里给一个简单可靠的双指针 partition 模板。先随机选一个位置 mid然后把 a[mid] 换到区间开头再之后的双指针划分只需要处理常规情况int partition(vectorint a, int l, int r) { int idx l rand() % (r - l 1); swap(a[l], a[idx]); int pivot a[l]; int i l 1, j r; while (true) { while (i r a[i] pivot) i; while (j l1 a[j] pivot) j--; if (i j) break; swap(a[i], a[j]); i; j--; } swap(a[l], a[j]); return j; }仔细看这个划分逻辑pivot 在 a[l]左右指针向中间靠拢遇到不满足条件的就交换。最终把 pivot 放回 j 位置。这样处理下来pivot 左边的元素都小于或等于它右边的元素都大于或等于它虽然等值元素的分布取决于实现但基准的随机性没有被破坏。注意很多“优化版快排”把 pivot 定为 a[mid] 然后直接和端点交换这不叫随机快排叫三数取中或固定的中间值策略。如果你要演示随机快排随机 index 必须真的参与 pivot 的选取。3.2 为什么很多子系统用三数取中而不是纯随机纯随机快排分析起来很干净但工程上主流排序库很少用纯随机。原因是 rand() 调用本身有开销而且 CPU 分支预测对随机 pivot 并不友好。一个经典改进是三数取中median-of-three加三路划分。这算不算随机快排严格说它不是“随机选择 pivot”但它吸收了随机化的核心思想尽量避免有序输入的恶意退化。某公司的排序库就有这么一段历史从老的“中点取 pivot”切换成三数取中后部分原本慢如蜗牛的有序/逆序数组直接起飞。三数取中选 pivot 的开销虽然多两次比较但它能让“近乎有序”和“逆序”的输入都不再触发最坏情况。而纯随机版本面对抗性更强理论上更安全。我的建议是如果你在写一个通用排序至少用三数取中如果你要教“随机快排”或在比赛里处理攻击性极强的数据用纯随机。纯随机的期望证明干净实际代码在某些平台上也很稳代价是随机数生成器的额外时间开销和较好的随机源要求。3.3 三路划分等值元素才是隐藏的性能杀手很多把随机快排写崩的场景不是 pivot 随机性不够而是数组里有大量重复元素。经典的二路划分处理 [1,1,1,1,1,1,1,1] 时如果 pivot 恰好是 1分区结果会一边倒吗取决于你的指针写法。像我上面给的模板pivot1 时左指针会因为 a[i] 1 不成立而停住右指针也停住然后交换两边几乎可以均匀推进。但有些单方向扫描版快排会在这个输入上退化到 O(n^2)。推荐工程上使用三路划分——把区间分成小于 pivot、等于 pivot、大于 pivot 三块只递归处理小于和大于两侧。随机选 pivot 加三路划分组合起来是处理重复元素和大数据量排序的黄金搭档。实现上有多种写法比二路划分稍微复杂一点但换来的稳定性非常值。void quickSort3(vectorint a, int l, int r) { if (l r) return; int idx l rand() % (r - l 1); swap(a[l], a[idx]); int pivot a[l]; int i l, j r, k l 1; // 区间 [l, i] 等于 pivot[i1, k-1] 小于 pivot[k, j] 待处理 while (k j) { if (a[k] pivot) { swap(a[i 1], a[k]); i; k; } else if (a[k] pivot) { swap(a[j], a[k]); j--; } else { k; } } swap(a[l], a[i]); i--; quickSort3(a, l, i); quickSort3(a, j 1, r); }这段代码中指针的语义容易写错建议自己拆开跑几步。核心原因在于等于 pivot 的元素要集中到中间这样重复多时递归规模能立刻缩小不会每层都面对几乎一样的子数组。4. 常见问题与排查实录4.1 为什么我测试的随机快排耗时涨成了抛物线遇到这个状况先别怀疑概率先检查你的随机数生成器。C 语言里经典的rand()在很多平台可生成的有效随机数位数有限或者容易被周期性问题干扰。再加上有些同学在快速排序的递归里直接调用rand() % (r-l1)当 n 很大时rand()的周期或者低位不均匀会让随机 index 出现明显偏差划分平衡度也随之变差。另一种可能是 partition 实现有 bug比如我只写过“单方向扫描版”int i l; for (int j l; j r; j) { if (a[j] pivot) swap(a[i], a[j]); }这版选最后一个元素做 pivot如果 pivot 随机化只体现在 swap 到末尾并且循环边界写错就很容易导致收缩区间不完整。排普通随机数组没问题但排大数组时性能明显不对。用我之前给的双指针模板可以规避这类边界 bug。4.2 重复元素跑慢了的经典案例我曾遇到过一份实测性能崩坏的随机快排代码数据里有大量“业务状态枚举值”总共就三五个不同的值。随机 pivot 选到的值经常是重复的二路划分把等值元素散落在两侧之后每层递归规模只缩小一点最后复杂度接近 O(n^2)。改用三路划分后同样的数据 10 万条排序只在毫秒级别完成。如果你处理的数据大概率有重复值至少把等于 pivot 的单独收集起来这样才能真正割掉“等于段”。经验遇到排序性能退化先跑一个大小固定的全等值数组。如果时间从几十毫秒涨到几秒八九不离十是划分策略不是三路而是普通二路且写得不平衡。4.3 如何用实验验证复杂度量级一个实用技巧不要只测一个规模要测多组规模并观察增长关系。例如在数据规模 n 和 2n、4n、8n 的情况下分别计时。如果是 O(n log n)时间会近似线性增长但比线性稍微快一点n 翻倍时间大概翻 2.2 倍左右如果是 O(n^2)n 翻倍时间会翻 4 倍左右。利用这个特征你可以快速在全球任何一台机器上测出一个实现大致是哪一级复杂度。构造“恶意输入”也值得试全正序数组、全逆序数组、全部相等数组、锯齿形数组比如递增递减交替。如果随机快排在所有输入上都保持稳定你才可以说它作为通用排序是合格的。我之前专门写过一个小工具用这些输入去回归测试排序库的耗时波动效果很好很多隐藏问题一测就显形。4.4 随机数生成器的质量影响有多大工程上建议使用伪随机数生成器而不是直接到处调用库函数里的 rand。很多语言标准库已经升级到高质量算法但老环境的rand()低位随机性不好。所以取模时要注意优先取高位或者用专门的随机库比如 C 的mt19937或者至少换一种方式构造随机数。否则在大规模排序时即使逻辑上对了随机性不足也会导致实测期望被拉高。我自己的代码里通常维护一个局部的随机对象避免在递归里频繁初始化或用全局锁。为此可以在排序函数外层传入随机数生成器递归调用时引用传递。5. 我踩过坑之后的一些体会这个题目看起来很基础可是因为它同时涉及数学期望、概率直觉、工程细节很容易被表面理解带偏。当年我第一次写随机快排时就是信了“随机了就一定 O(n log n)”结果测试时用了大量重复值排序耗时飞升一度以为自己的随机化是假的。后来才搞明白随机化解决的是对阵恶劣输入的概率问题而重复元素问题是另一个独立的工程维度需要三路划分协作。后来又经历了几次把递归深度打印出来排查性能翻车现场才彻底形成经验评估排序性能别只看平均数据要把最坏输入、重复值、递归深度、随机源质量都考虑进去。如果你在准备面试我建议你至少能手推一遍指示器变量的期望证明并且能写出三路划分随机快排的无 bug 版本这两件事都做到了任何问到快排复杂度的场合你都能聊透。最后分享一个我自己觉得特别顺手的调试方法给排序算法加一个宏开关打印递归深度和子区间长度能在第一时间暴露划分平衡度问题。正序、逆序、等值、随机四组测试一起跑任何随机快排实现是骡子是马都看得清清楚楚。这方法不复杂但比盯着几百行代码找逻辑快多了。