快速排序

前言：另一种分治的思路

在归并排序那篇笔记里，我们学了”先递归，再合并”的分治思路。快速排序是同一个硬币的另一面：先分区，再递归。

回到排队的问题。这次换一种方法：随便选一个人做标杆（pivot），比他矮的站左边，比他高的站右边。标杆站在中间，位置就确定了——他左边的人都比他矮，右边都比他高。然后对左右两组分别做同样的事。

这个方法看起来和归并排序差不多，但有一个妙处：分区操作是原地的——不需要额外的数组，只需要在原数组上交换。而且如果运气好（每次标杆都选在中间），深度只有 $\log n$ 层，每层扫一遍 $n$ 个元素，总共 $O(n \log n)$。

快速排序是实际工程中最常用的排序算法（大多数语言的 sort 底层就是它），因为它常数极小。同时，把”两侧都递归”改成”只递归一侧”，就能得到 QuickSelect——$O(n)$ 找第 $k$ 大元素的算法。这篇笔记最后会展示这个技巧。

快速排序

问题的本质

给定 $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);
}

例题：数组中的第 K 大元素

给定长度 $n$ 的数组，求第 $k$ 大的元素（$1 \le k \le n$）。

排序后取第 $k$ 个是 $O(n \log n)$。但利用 Partition 的性质可以做到期望 $O(n)$——这就是 QuickSelect。

Partition 把 pivot 放到它最终排序后的位置 $p$。如果 $p$ 恰好是我们要找的位置，直接返回；否则只递归包含目标位置的那一侧。

int quickselect(vector<int>& a, int l, int r, int k) {
    if (l == r) return a[l];
    int idx = l + rand() % (r - l + 1);
    swap(a[idx], a[r]);

    int pivot = a[r], i = l;
    for (int j = l; j < r; j++)
        if (a[j] >= pivot) swap(a[i++], a[j]);  // 降序排，第 k 大
    swap(a[i], a[r]);

    int rank = i - l + 1;        // pivot 是当前区间第几大
    if (rank == k) return a[i];
    if (rank > k)  return quickselect(a, l, i - 1, k);
    return quickselect(a, i + 1, r, k - rank);
}

解析：每次 Partition 后只递归一侧，所以期望时间 $O(n) + O(n/2) + O(n/4) + \dots = O(n)$。随机化保证不会退化为 $O(n^2)$。和快速排序唯一的区别就是：快排两侧都递归，QuickSelect 只递归一侧。