快速排序

快速排序 (Quick Sort)

快速排序 (Quick Sort) 是一种基于分治策略 (Divide and Conquer) 的比较排序算法，由英国计算机科学家 C. A. R. Hoare 于 1959 年提出，1961 年正式发表。快速排序在平均情况下具有 $O(n \log n)$ 的时间复杂度，且常数因子较小，在实践中通常优于归并排序和堆排序等同样具有 $O(n \log n)$ 复杂度的算法，被广泛视为通用排序算法中的首选方案。

核心思想

快速排序的核心思想是：每次从待排序数组中选取一个基准元素 (Pivot)，通过一趟扫描将数组划分为两个子数组——左侧所有元素均小于等于基准，右侧所有元素均大于等于基准——然后对左右子数组递归执行相同操作，直至子数组长度为 0 或 1，此时自然有序。一趟完整的划分操作称为 Partition。

算法步骤

给定数组 $A$ 及待排序区间 $[l, r]$：

1. 若 $l \geq r$，区间长度不超过 1，直接返回（递归基）。
2. 选取基准元素，设其索引为 $p$。
3. 执行 Partition：重排 $A[l..r]$，使小于基准的元素位于左侧、大于基准的位于右侧，返回基准最终位置 $q$。
4. 递归排序左子数组 $A[l..q-1]$ 和右子数组 $A[q+1..r]$。

划分方案

Partition 有两种经典实现：

Lomuto 方案

选取区间末尾元素为 pivot，单指针扫描。维护指针 $i$ 作为「小于等于 pivot 区域」的右边界，遍历 $j$ 从 $l$ 到 $r-1$，每当 $A[j] \leq \text{pivot}$，递增 $i$ 并交换 $A[i]$ 与 $A[j]$。遍历结束后将 pivot 交换至 $i+1$ 位置。实现简洁，但平均交换次数多于 Hoare 方案。

Hoare 方案

采用双指针从两端向中间扫描：左指针 $i$ 右移直至遇到不小于 pivot 的元素，右指针 $j$ 左移直至遇到不大于 pivot 的元素；若 $i \geq j$ 返回 $j$ 作为分割点，否则交换 $A[i]$ 与 $A[j]$ 并继续。平均交换次数更少，实践中效率更高。

时间复杂度分析

性能高度依赖于基准选择：

• 最优情况：每次均分数组，递归深度 $\log_2 n$，每层 $O(n)$，总复杂度 $O(n \log n)$。
• 平均情况：期望复杂度 $O(n \log n)$，常数因子（约 $1.39 \log_2 n$ 次比较）优于归并排序和堆排序。
• 最坏情况：每次基准恰为当前区间极值（如已有序数组），递归深度退化为 $n$，复杂度恶化至 $O(n^2)$。

优化策略

针对最坏情况的脆弱性，常见优化包括：

1. 随机化基准选择：每次 Partition 前随机选取元素与区间末尾交换，使最坏情况概率极低。此变体称随机化快速排序 (Randomized Quick Sort)，期望复杂度 $O(n \log n)$。
2. 三数取中法 (Median-of-Three)：取区间首、尾、中间三元素的中位数为基准，显著降低有序数组的退化风险。
3. 小数组切换：子数组长度小于阈值（通常 10--20）时改用插入排序，因其在小规模数据上常数极小且无递归开销。
4. 三路划分 (Three-Way Partitioning)：存在大量重复元素时，将数组划分为小于、等于、大于 pivot 三部分，避免重复处理。由 Dijkstra 提出。

空间复杂度与稳定性

快速排序是原地排序：Partition 仅需 $O(1)$ 额外空间。递归栈深度最坏 $O(n)$，平均 $O(\log n)$；通过尾递归优化——每次优先处理较短侧，较长侧迭代处理——可严格控制在 $O(\log n)$。

快速排序是不稳定排序：交换可能改变相等元素的相对顺序。如需稳定排序，应选用归并排序。

尽管存在最坏退化风险和稳定性缺失，快速排序凭借出色的平均性能、原地特性和小常数因子，仍是大多数标准库的核心排序引擎——C++ 标准模板库的 \texttt{std::sort} 通常采用内省排序 (Introsort)，即快速排序、堆排序和插入排序的混合变体。它也是算法课程中分治策略的经典教学案例。