跳到主要内容

AcWing 785. 快速排序

本节目标

用 Hoare 双指针分区递归完成原地快速排序，并保证重复值也会推进。

这道题是排序与选择的起点：先把一个区间按枢轴分成两侧，再递归处理两侧。

查看 AcWing 原题

题意与约束​

给定 n 个整数，按非递减顺序输出它们。数组可以包含负数和重复值。

朴素思路与瓶颈​

逐个确定输出位置、每次在剩余元素中寻找最小值也能排序，但第一个位置检查 n 个数，之后仍要反复扫描，总时间为 O(n²)。快速排序改用一次线性分区批量确定两侧的大小关系，再递归处理子区间。

分区循环不变量​

取中点位置的值作为 pivot。i 从 left - 1 开始向右寻找第一个不小于 pivot 的值，j 从 right + 1 开始向左寻找第一个不大于 pivot 的值。交换前，[left, i) 都小于 pivot，(j, right] 都大于 pivot；交换后，这两个已确认区域继续扩大。

当 i >= j 时，左区间 [left, j] 中没有元素大于 pivot，右区间 [j + 1, right] 中没有元素小于 pivot。因此递归处理这两个区间即可。

为什么重复值不会卡住​

指针移动使用先执行一次的推进逻辑。等于 pivot 的元素会让本轮停下，但若 i < j 就会交换，下一轮两个指针仍会继续推进；它们不会反复停在同一位置。分界点 j 位于原区间内部，递归区间严格缩小，最终必然到达单元素或空区间。

代码实现​

C++ 把输入规模 n 和主数组 nums 定义为全局变量，递归函数 quickSort(left, right) 只传递当前区间边界，并原地修改全局数组；main 只负责读入、调用与输出。Python 保留更自然的数组参数写法。两种语言使用相同的中点枢轴和双指针分区。这是完整竞赛程序的模板表达方式，不代表通用函数或工程代码也应默认使用全局变量。

C++17
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int n;
vector<int> nums;

void quickSort(int left, int right) {
    if (left >= right) {
        return;
    }

    const int pivot = nums[left + (right - left) / 2];
    int i = left - 1;
    int j = right + 1;
    while (true) {
        do {
            i++;
        } while (nums[i] < pivot);
        do {
            j--;
        } while (nums[j] > pivot);
        if (i >= j) {
            break;
        }
        swap(nums[i], nums[j]);
    }

    quickSort(left, j);
    quickSort(j + 1, right);
}

int main() {
    cin >> n;
    nums.resize(n);
    for (int& x : nums) {
        cin >> x;
    }

    quickSort(0, n - 1);
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << nums[i];
    }
    return 0;
}

复杂度分析​

  • 平均时间复杂度：O(n log n)。
  • 最坏时间复杂度：O(n²)；不平衡分区会使递归退化。
  • 额外空间复杂度：平均为 O(log n) 的递归栈。

易错点​

  • i 应从 left - 1、j 应从 right + 1 起步。
  • 分区结束后递归的是 [left, j] 与 [j + 1, right]。
  • 不要把枢轴保存为会被交换的位置，应保存其值。

模式迁移​

快速排序的可复用部分是双指针分区。第 k 小、按阈值划分和三路分组都先问：分区完成后，哪一侧已经可以不再处理？