快速排序

为什么需要快速排序

快速排序是所有内部排序算法中平均性能最优的排序算法，被认为是 20 世纪十大算法之一。它基于分治策略，在绝大多数场景下的实际运行速度优于归并排序和堆排序。

408 考研中，快速排序是排序章节考频最高的算法，选择题、填空题、算法题均可能涉及。理解其分区过程、递归结构和最坏情况是得分关键。

核心思想

快速排序的核心是分治法（Divide and Conquer）：

分区（Partition）：从待排序序列中选一个元素作为基准（pivot），将序列划分为两部分——左边所有元素 ≤ pivot，右边所有元素 ≥ pivot
递归（Recurse）：对左、右两个子序列分别递归执行快速排序
合并（Combine）：无需额外合并操作，分区完成后序列自然有序

一趟排序的效果：pivot 被放到了最终位置，这是快速排序区别于其他排序的关键特征。

交互可视化

通过下方的交互动画，你可以逐步观察快速排序的执行过程：

加载可视化中...

操作详解

算法思路

快速排序的主框架非常简洁：

cpp

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 左边都 ≤ 它，右边都 ≥ 它）

cpp

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 的位置
}

示例：对序列 [49, 38, 65, 97, 76, 13, 27] 执行一趟划分（pivot = 49）：

初始:  [49] 38  65  97  76  13  27
       low                      high

第1轮: 27  38  65  97  76  13  [49]    ← high 找到 27，移到 low
       27  38  65  97  76  13  [65]    ← low 找到 65，移到 high

第2轮: 27  38 [13] 97  76 [65] 65     ← high 找到 13，移到 low
       27  38  13 [97] 76  65  65     ← low 找到 97，移到 high
       27  38  13 [76] 97  65  65     ← ...继续

结果:  27  38  13  [49]  76  97  65
                    ↑ pivot 到达最终位置

递归分析

快速排序的递归过程可以用递归树来理解：

最好情况：每次 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²)

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)	递归栈的深度

其他性质：

性质	结论
稳定性	不稳定（分区交换可能改变相同元素的相对顺序）
适用场景	数据量大且基本无序时效率最高
是否原地排序	是（不计递归栈空间）
每趟结果特征	一趟排序确定一个元素的最终位置

考研高频考点

⭐ 手动模拟一趟 Partition 过程，写出划分结果（选择题/填空题必考）
⭐ 快速排序的时间复杂度（最好、最坏、平均）及其推导（选择题/简答题高频）
⭐ 快速排序是不稳定排序（举反例说明）
⭐ 最坏情况何时发生（初始序列有序 + 取首元素为 pivot）
⭐ 每趟排序至少确定一个元素的最终位置（判断某趟排序后的序列是否可能是快排的结果）
快速排序的空间复杂度为 O(log₂n)～O(n)，来自递归栈
pivot 优化策略（随机化、三数取中）
快速排序与其他 O(nlog₂n) 排序（归并、堆排）的对比

交互体验

前往完整可视化页面 →

巩固练习

刷题平台即将推出，敬请期待...

快速排序 ​

为什么需要快速排序 ​

核心思想 ​

交互可视化 ​

操作详解 ​

算法思路 ​

分区过程 ​

递归分析 ​

最坏情况分析 ​

复杂度分析 ​

考研高频考点 ​

相关文章