快速排序

💡 打个比方

体育老师集合队伍："报数！比我矮的站左边，比我高的站右边。"哨兵老师往中间一站，队伍立刻分成两堆：左边全是比哨兵矮的，右边全是比哨兵高的——哨兵的位置就此确定，再也不会动。

然后左边那堆里再挑一个哨兵，重复"矮左高右"；右边那堆也一样。每选一个哨兵，就有一个同学站到了最终位置，剩下的问题变成两个更小的一半。

快速排序 = 选哨兵（pivot）+ 一次扫描把"比哨兵小的"换到左边、"大的"留在右边 + 递归排左右两半。它和归并排序一样平均 O(n log n)，而且原地排序、不需要辅助数组——但哨兵选得不好（比如已经排好的数组还总拿第一个当哨兵），每轮只"切掉"一个，会退化成 O(n²)。

🖼️ 大图看明白

📏 怎么写快排：只要 3 步

第 1 步：选哨兵——取 a[l]（第一个元素）当哨兵。哨兵的职责是：一轮扫描后站到最终位置。

第 2 步：partition 扫描——指针 i 守住"小区"的边界（a[l+1..i] 都小于哨兵），j 从 l+1 扫到 r：a[j] < 哨兵就把 a[j] 和 a[i+1] 交换、i 前进一位；a[j] ≥ 哨兵就原地不动。扫完后小区 [l+1, i] 全小、[i+1, r] 全大。

第 3 步：放哨兵 + 递归——把哨兵和 a[i] 交换，哨兵落到最终位置 i；然后对 [l, i-1] 和 [i+1, r] 各自递归快排。基本情况：l >= r（区间长度 1）直接返回。

💻 C++ 怎么写

int a[105], n;
// partition：拿第一个当哨兵，小的换到左边
int partition(int l, int r) {
    int pivot = a[l];       // 哨兵
    int i = l;              // a[l+1..i] 都小于哨兵
    for (int j = l + 1; j <= r; j++) {
        if (a[j] < pivot) {
            int t = a[i+1]; a[i+1] = a[j]; a[j] = t;  // 小的换进小区
            i++;
        }
    }
    int t = a[l]; a[l] = a[i]; a[i] = t;  // 哨兵落到边界
    return i;               // 哨兵的最终位置
}
// 分治：左右两半各自递归
void quickSort(int l, int r) {
    if (l >= r) return;    // 基本情况：长度 1
    int p = partition(l, r);
    quickSort(l, p - 1);   // 左半（全比哨兵小）
    quickSort(p + 1, r);   // 右半（全比哨兵大）
}

✋ 你来试试