为什么快速排序最坏情况$O(n^2)$但平均$O(n \log n)$：概率分析

快速排序是实践中使用最广泛的排序算法之一。它的平均时间复杂度是 $O(n \log n)$，但最坏情况下会退化为 $O(n^2)$。这个性能差异让许多人感到困惑：为什么同一个算法会有如此大的表现波动？答案隐藏在主元选择的随机性中。

1. 理解快速排序的核心机制

快速排序的工作流程可以分解为三个反复执行的步骤。

1. 选择 一个元素作为主元（pivot）
2. 划分 数组，使得所有小于主元的元素移入其左侧，所有大于主元的元素移入其右侧
3. 递归 对左右两个子数组重复 执行 步骤1和步骤2

关键观察：算法的效率完全取决于划分的平衡程度。如果每次划分都将数组分成两个大小相近的部分，递归树的深度就是 $\log n$，每层需要处理 $n$ 个元素，总时间就是 $O(n \log n)$。如果划分严重失衡，递归树就会变得又细又长。

2. 拆解最坏情况 $O(n^2)$ 的成因

最坏情况发生在每次选择的主元都是当前子数组的最小值或最大值时。此时，每次划分只能将一个元素放到正确位置，另一个子数组的长度只比原数组少1。

2.1 从递归关系看时间增长

假设每次划分后，一个子数组大小为0，另一个子数组大小为 n-1。递归的时间公式为：

$$T(n) = T(n-1) + n$$

这个递推式的含义是：处理 n 个元素的时间，等于处理 n-1 个元素的时间，加上本次划分需要比较的 n 次。

2.2 推导最坏情况的总时间

将递推式层层展开：

$$T(n) = T(n-1) + n$$
$$T(n-1) = T(n-2) + (n-1)$$
$$\cdots$$
$$T(1) = 1$$

将上述等式全部相加，左右抵消后：

$$T(n) = n + (n-1) + (n-2) + \cdots + 1 = \frac{n(n+1)}{2}$$

忽略常数和低阶项，得到 $O(n^2)$。

触发条件：最坏情况通常出现在数组已经有序或逆序，并且每次选择第一个或最后一个元素作为主元时。如果输入完全有序，每次选择第一个元素，子问题大小就是这样依次递减。

3. 追踪平均情况 $O(n \log n)$ 的概率逻辑

平均情况分析假设输入数据是随机排列的，并且主元等可能地落在数组的任何一个位置。这是概率分析的核心前提。

3.1 用随机变量定义比较次数

定义随机变量 $X$ 为快速排序执行过程中进行的总比较次数。目标是计算 $E[X]$，即 $X$ 的期望值。

核心技巧：将总比较次数分解为每一对元素之间被比较的概率之和。定义指示变量 $X_{ij}$，当第 $i$ 小的元素和第 $j$ 小的元素 ($i < j$) 在排序过程中被比较时，$X_{ij}=1$，否则 $X_{ij}=0$。

$$X = \sum_{i=1}^{n} \sum_{j=i+1}^{n} X_{ij}$$

3.2 计算一对元素被比较的概率

两个元素 $i$ 和 $j$ 只有在其中一个被选为主元，且此时它们仍处于同一个子数组中时，才会被比较。更重要的是，如果它们之间的某个元素先被选为主元，它们就会被分到不同子数组，永远不会再比较。

关键推理：在元素 $i, i+1, \ldots, j$ 这一集合中，任一个元素被选为主元的概率相等，都是 $\frac{1}{j-i+1}$。只有 $i$ 或 $j$ 被选为主元时，它们才会发生比较；如果中间某个元素被选为主元，$i$ 和 $j$ 就被分开了。

因此，一对元素被比较的概率为：

$$P(X_{ij} = 1) = \frac{2}{j - i + 1}$$

3.3 计算总比较次数的期望

对期望值求和：

$$E[X] = \sum_{i=1}^{n} \sum_{j=i+1}^{n} \frac{2}{j - i + 1}$$

引入变量 $k = j - i + 1$，当 $i$ 固定时，$k$ 从 $2$ 取到 $n-i+1$。改写内层求和：

$$E[X] = \sum_{i=1}^{n} \sum_{k=2}^{n-i+1} \frac{2}{k}$$

用自然对数近似调和级数 $H_n = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \approx \ln n$，可得：

$$E[X] \approx 2n \ln n = O(n \log n)$$

数学直觉：虽然最坏情况每次划分都是极端失衡，但从概率角度看，这种极端事件发生的概率极低。在随机输入下，大多数划分都接近平衡，因此期望性能远好于最坏情况。

4. 平衡概率差异的关键机制

最坏情况和平均情况的分水岭在于主元在数组中的位置分布。

最坏场景：主元始终位于数组的端部（第1或第n个位置）。此时划分的平衡度为 1 对 n-1，递归深度为 $n$。

平均场景：主元落在数组中间 50% 区域（即第 $\frac{n}{4}$ 到 $\frac{3n}{4}$ 之间）的概率为 $\frac{1}{2}$。一旦主元落在此区间内，划分比例就在 $1:3$ 到 $3:1$ 之间，递归深度为 $O(\log_{4/3} n) = O(\log n)$。

即使偶尔出现一次失衡划分，只要不连续出现，下一轮随机选择就会大概率将其拉回平衡。这种随机性带来的自修复能力保证了平均性能。

实际验证：运行快速排序100次，记录每次的比较次数。对随机数据，比较次数几乎总是在 $1.39n \log n$ 附近波动（$1.39$ 是 $2\ln 2$ 的近似值），极少出现接近 $\frac{n^2}{2}$ 的情况。

5. 消除最坏情况的工程实践

虽然概率分析表明最坏情况很少发生，但在关键系统中，仍然需要防范恶意输入导致的性能崩溃。有三种主流的防范策略。

1. 随机化主元选择：在划分前，从数组中随机抽取一个元素作为主元。这样，即使输入是有序排列，主元位置也是随机的，最坏情况发生的概率降为 $\frac{1}{n!}$。
2. 三数取中法：选择数组第一个、中间和最后一个元素的中位数作为主元。这种方法能快速绕过有序输入的陷阱，且几乎不增加额外计算开销。
3. 切换到插入排序：当子数组长度小于某个阈值（如16）时，替换为插入排序。插入排序在小规模数据上效率更高，且避免了递归的额外成本。