快速排序

快速排序

问题的本质

给定 $n$ 个元素，如何在 $O(n \log n)$ 时间内将它们排成有序？

朴素做法（选择、插入）都是 $O(n^2)$。瓶颈在于每次操作只能利用一个元素的局部信息，没有把问题的规模真正缩小。

关键洞察：如果我们能把所有元素按某个标准分成”小的一组”和”大的一组”，那么两组各自排序后直接拼接就是整体有序——分治。

这就是快速排序的全部思想：选一个基准（pivot），把比它小的放左边、比它大的放右边，然后对两边递归做同样的事。

核心操作：Partition

快速排序的灵魂是 Partition。给定数组的一段区间 $[l, r]$ 和一个 pivot 值，把区间重排成：

$$\underbrace{\le \text{pivot}}_{\text{左半}} \quad \text{pivot} \quad \underbrace{> \text{pivot}}_{\text{右半}}$$

Lomuto 分区（单指针，代码最简洁）：

int partition(vector<int>& a, int l, int r) {
    int pivot = a[r];          // 选最右元素为 pivot
    int i = l;                 // i 左边全是 ≤ pivot 的
    for (int j = l; j < r; j++) {
        if (a[j] <= pivot) {
            swap(a[i], a[j]);  // 把小的换到前面
            i++;
        }
    }
    swap(a[i], a[r]);          // pivot 归位
    return i;                  // 返回 pivot 的最终位置
}

过程很简单：指针 j 扫过整个区间，每遇到一个 $\le$ pivot 的元素就把它和 a[i] 交换，然后 i++。扫描结束后 a[i] 的左边全 $\le$ pivot、右边全 $>$ pivot，把 pivot 换到 a[i] 即可。

完整的快速排序

void quicksort(vector<int>& a, int l, int r) {
    if (l >= r) return;              // 0 或 1 个元素，已有序
    int p = partition(a, l, r);      // 分区，pivot 归位
    quicksort(a, l, p - 1);          // 排左半
    quicksort(a, p + 1, r);          // 排右半
}

就这样。Partition + 递归，没了。

复杂度分析

最好情况：每次 pivot 恰好把区间等分。

$$T(n) = 2T(n/2) + O(n) \implies T(n) = O(n \log n)$$

Partition 扫一遍是 $O(n)$，递归深度 $\log n$，每层总工作量 $O(n)$。

最坏情况：每次 pivot 都是最大或最小值（比如数组已经有序），一边为空，另一边是 $n-1$。

$$T(n) = T(n-1) + O(n) \implies T(n) = O(n^2)$$

平均情况：随机选 pivot 时，期望深度为 $O(\log n)$，总期望时间 $O(n \log n)$。

防止最坏情况：随机化

最坏情况的根源是 pivot 选得差。解法很暴力——随机选：

int partition(vector<int>& a, int l, int r) {
    int idx = l + rand() % (r - l + 1);  // 随机选一个位置
    swap(a[idx], a[r]);                   // 换到最右，其余不变
    int pivot = a[r];
    int i = l;
    for (int j = l; j < r; j++) {
        if (a[j] <= pivot) {
            swap(a[i++], a[j]);
        }
    }
    swap(a[i], a[r]);
    return i;
}

随机化之后，任何特定输入都不会稳定触发最坏情况。期望 $O(n \log n)$，常数极小，实际运行往往是所有 $O(n \log n)$ 排序中最快的。

Hoare 分区（双指针，更快）

Lomuto 每次都 swap，对小元素很多的数组效率偏低。Hoare 的思路是两端同时向中间扫，遇到”左边有大的、右边有小的”就交换：

int partition(vector<int>& a, int l, int r) {
    int pivot = a[l + (r - l) / 2];  // 取中间元素为 pivot
    int i = l - 1, j = r + 1;
    while (true) {
        do { i++; } while (a[i] < pivot);  // 找左边 ≥ pivot 的
        do { j--; } while (a[j] > pivot);  // 找右边 ≤ pivot 的
        if (i >= j) return j;              // 指针相遇，分区完成
        swap(a[i], a[j]);
    }
}

swap 次数更少，且内层循环是 do-while（即使 a[i] == pivot 也会停下），天然减少了不平衡分区的概率。

注意 Hoare 返回的 j 不一定是 pivot 的精确位置，所以递归写法略有不同：

void quicksort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int p = partition(a, l, r);
    quicksort(a, l, p);       // 注意是 p 不是 p-1
    quicksort(a, p + 1, r);
}