Appearance
快速排序
快排为什么是标准库首选
同样是 O(n log n)，为什么 C 标准库的 qsort、Java 的 Arrays.sort（基本类型）、C++ 的 std::sort 底层都选了快速排序，而不是归并或堆排？答案藏在常数因子里——快排的内层循环只做一次比较和一次赋值，cache 命中率也更高。
408 考研中，快速排序是排序章节考频最高的算法，选择题、填空题、算法题均可能涉及。理解其分区过程、递归结构和最坏情况是得分关键。
核心思想
快速排序的核心是分治法（Divide and Conquer）：
- 分区（Partition）：从待排序序列中选一个元素作为基准（pivot），将序列划分为两部分——左边所有元素 ≤ pivot，右边所有元素 ≥ pivot
- 递归（Recurse）：对左、右两个子序列分别递归执行快速排序
- 合并（Combine）：无需额外合并操作，分区完成后序列自然有序
一趟排序的效果：pivot 被放到了最终位置，这是快速排序区别于其他排序的关键特征。
交互可视化
通过下方的交互动画，你可以逐步观察快速排序的执行过程：
操作详解
算法思路
快速排序的主框架非常简洁：
c
void QuickSort(int A[], int low, int high) {
if (low < high) {
int pivotPos = Partition(A, low, high); // 划分
QuickSort(A, low, pivotPos - 1); // 排左子表
QuickSort(A, pivotPos + 1, high); // 排右子表
}
}整个算法的核心在于 Partition 函数的实现。
分区过程
以第一个元素为基准（pivot），使用双指针 low 和 high 从两端向中间扫描：
- 将 pivot 暂存（
pivot = A[low]） high从右向左找到第一个 < pivot 的元素，放到low位置low从左向右找到第一个 > pivot 的元素，放到high位置- 重复步骤 2-3，直到
low == high - 将 pivot 放入
low位置（此时 pivot 左边都 ≤ 它，右边都 ≥ 它）
c
int Partition(int A[], int low, int high) {
int pivot = A[low]; // 取第一个元素为基准
while (low < high) {
while (low < high && A[high] >= pivot)
high--;
A[low] = A[high]; // 比 pivot 小的移到左端
while (low < high && A[low] <= pivot)
low++;
A[high] = A[low]; // 比 pivot 大的移到右端
}
A[low] = pivot; // pivot 放到最终位置
return low; // 返回 pivot 的位置
}⚠️ 易错：Partition 中 while 条件的
>=和<=不能改成>和<，否则当序列中存在与 pivot 相等的元素时，两个指针都不会移动，导致死循环。
示例：对序列 [49, 38, 65, 97, 76, 13, 27] 执行一趟划分（pivot = 49）：
| 步骤 | low | high | 动作 | 数组状态 |
|---|---|---|---|---|
| 初始 | 0 | 6 | pivot = A[0] = 49，暂存 pivot | [49, 38, 65, 97, 76, 13, 27] |
| 1 | 0 | 6 | high 扫描：A[6]=27 < 49，停。A[0]=A[6] | [27, 38, 65, 97, 76, 13, 27] |
| 2 | 0 | 6 | low 扫描：A[0]=27 ≤ 49，low++ | [27, 38, 65, 97, 76, 13, 27] |
| 3 | 1 | 6 | low 扫描：A[1]=38 ≤ 49，low++ | [27, 38, 65, 97, 76, 13, 27] |
| 4 | 2 | 6 | low 扫描：A[2]=65 > 49，停。A[6]=A[2] | [27, 38, 65, 97, 76, 13, 65] |
| 5 | 2 | 6 | high 扫描：A[6]=65 ≥ 49，high-- | [27, 38, 65, 97, 76, 13, 65] |
| 6 | 2 | 5 | high 扫描：A[5]=13 < 49，停。A[2]=A[5] | [27, 38, 13, 97, 76, 13, 65] |
| 7 | 2 | 5 | low 扫描：A[2]=13 ≤ 49，low++ | [27, 38, 13, 97, 76, 13, 65] |
| 8 | 3 | 5 | low 扫描：A[3]=97 > 49，停。A[5]=A[3] | [27, 38, 13, 97, 76, 97, 65] |
| 9 | 3 | 5 | high 扫描：A[5]=97 ≥ 49，high-- | [27, 38, 13, 97, 76, 97, 65] |
| 10 | 3 | 4 | high 扫描：A[4]=76 ≥ 49，high-- | [27, 38, 13, 97, 76, 97, 65] |
| 11 | 3 | 3 | low == high，退出循环。A[3] = pivot | [27, 38, 13, 49, 76, 97, 65] |
最终结果：pivot = 49 到达下标 3，左侧 [27, 38, 13] 均 ≤ 49，右侧 [76, 97, 65] 均 ≥ 49。
递归分析
快速排序的递归过程可以用递归树来理解：
- 最好情况：每次 pivot 恰好将序列等分为两半，递归树是一棵平衡二叉树，树高为 log₂n，每层总共比较 n 次，因此总时间复杂度为 O(nlog₂n)
- 最坏情况：每次 pivot 都是当前序列的最大或最小值，一侧子序列为空，递归树退化为单链，树高为 n，总时间复杂度为 O(n²)
递归调用需要栈空间来保存每层的参数：
- 最好情况栈深度：O(log₂n)
- 最坏情况栈深度：O(n)
最坏情况分析
最坏情况发生在**序列基本有序（正序或逆序）**时：
- 若序列已经有序且每次取第一个元素为 pivot，则 pivot 就是最小值，左子表为空，右子表有 n-1 个元素
- 每趟只能确定一个元素的位置，需要 n-1 趟
- 比较次数：n-1 + n-2 + ... + 1 = n(n-1)/2 = O(n²)
⚠️ 易错：'快排最坏 O(n²)'不意味着快排不好。408 选择题常考：'对任意输入数据，以下哪种排序算法最坏情况仍为 O(n log n)？'——答案是归并和堆排，快排不在其中。
pivot 优化策略（降低最坏情况出现概率）：
- 随机选取 pivot：从当前子序列中随机选一个元素与
A[low]交换，再执行标准 Partition - 三数取中法：取
A[low]、A[mid]、A[high]三者的中值作为 pivot，有效避免有序输入导致的退化 - 当子序列较短时改用直接插入排序：递归到小规模子问题时，插入排序的常数因子更小，效率更高
复杂度分析
| 指标 | 最好情况 | 平均情况 | 最坏情况 | 说明 |
|---|---|---|---|---|
| 时间复杂度 | O(nlog₂n) | O(nlog₂n) | O(n²) | 平均性能最优的内部排序 |
| 空间复杂度 | O(log₂n) | O(log₂n) | O(n) | 递归栈的深度 |
其他性质：
| 性质 | 结论 |
|---|---|
| 稳定性 | 不稳定（分区交换可能改变相同元素的相对顺序） |
| 适用场景 | 数据量大且基本无序时效率最高 |
| 是否原地排序 | 是（不计递归栈空间） |
| 每趟结果特征 | 一趟排序确定一个元素的最终位置 |
⚠️ 易错：'每趟确定一个元素的最终位置'是快排的独有特征。408 真题常给出某趟排序后的序列，问'可能是以下哪种排序的结果'——如果恰好有一个元素到达了最终位置（左边都比它小，右边都比它大），就可能是快排。但注意：冒泡排序每趟也能确定一个元素（最大或最小），区别在于冒泡确定的是全局最大/最小值，快排确定的不一定是。
考研高频考点
- ⭐ 手动模拟一趟 Partition 过程，写出划分结果（选择题/填空题必考）
- ⭐ 快速排序的时间复杂度（最好、最坏、平均）及其推导（选择题/简答题高频）
- ⭐ 快速排序是不稳定排序（举反例说明）
- ⭐ 最坏情况何时发生（初始序列有序 + 取首元素为 pivot）
- ⭐ 每趟排序至少确定一个元素的最终位置（判断某趟排序后的序列是否可能是快排的结果）
- 快速排序的空间复杂度为 O(log₂n)～O(n)，来自递归栈
- pivot 优化策略（随机化、三数取中）
- 快速排序与其他 O(nlog₂n) 排序（归并、堆排）的对比
相关知识
- 快排的 Partition 思想也用于快速选择算法（Quick Select），O(n) 时间找第 k 小元素——这是 Partition 的另一个重要应用
- 快排在子序列较短时常切换为直接插入排序，因为小规模数据下插入排序的常数因子更小
- 快排的递归结构与归并排序形成对比：快排是"先处理再递归"（先 partition 后递归子表），归并是"先递归再处理"（先递归子表后合并）
- 快排的空间复杂度来自递归栈，与堆排序的 O(1) 空间形成对比——这是选择排序算法时的重要权衡