快速排序选定一个枢轴元素 pivot，将数组划分为两部分：

• 左边均小于等于 pivot；
• 右边均大于等于 pivot；

然后递归处理左右两侧。

Ph1zの理解： 快排的核心就一件事——选标杆，分两边。标杆左边的都比它矮，右边的都比它高，标杆自己已经站在最终位置了。然后左右两边各自再选标杆……分到不能再分，排序就完成了。简单粗暴，但非常高效喵

代码

int partition(int a[], int l, int r) {
    int pivot = a[r];
    int i = l - 1;
    for (int j = l; j < r; ++j) {
        if (a[j] <= pivot) {
            ++i;
            std::swap(a[i], a[j]);
        }
    }
    std::swap(a[i + 1], a[r]);
    return i + 1;
}

void quickSort(int a[], int l, int r) {
    if (l >= r) return;
    int p = partition(a, l, r);
    quickSort(a, l, p - 1);
    quickSort(a, p + 1, r);
}

正确性证明

设分区函数返回位置 p，则：

• 所有 a[l..p-1] <= a[p]；
• 所有 a[p+1..r] >= a[p]；
• a[p] 已处于最终位置。

证明思路：

• 扫描过程中，i 维护"已放置到左边的较小元素"位置的下界；
• 每遇到一个不大于 pivot 的元素，就放到 i+1 位置，保证左边区间全都满足条件；
• 最后把 pivot 交换到 i+1 位置，得到正确的分界。

随后递归处理左右两边，最终整个数组有序。 ✓

Ph1zの理解： partition 就像体育课排队——选一个人当标杆，比他矮的站左边，比他高的站右边。标杆自己不用再动了。然后左右两队再各选标杆……直到每队只有 0 或 1 个人。

复杂度分析

情况	递推式	时间复杂度	直觉
最好	$T(n)=2T(n/2)+O(n)$	$O(n\log n)$	每次均匀划分，和归并排序一样
最坏	$T(n)=T(n-1)+O(n)$	$O(n^2)$	枢轴总是最值，退化为逐个扫描
平均	随机划分	$O(n\log n)$	大部分划分比较均匀

最坏情况怎么来的？ 如果数组已经有序，而每次选最后一个元素做 pivot，那么左边是空集，右边是 $n-1$ 个元素——每层只减少一个元素，递归深度 $n$，每层工作量 $O(n)$，总计 $O(n^2)$。这在实际中是可能发生的！

额外空间： 递归栈 $O(\log n)$（平均），但最坏递归深度可达 $O(n)$。

稳定性： 不稳定。因为在分区交换过程中，等值元素可能跨过对方交换位置，顺序被打乱。

实战优化： 工程上常用以下策略降低退化概率：

策略	说明	效果
随机枢轴	swap(a[r], a[rand()])	期望均匀划分
三数取中	取 a[l], a[mid], a[r] 的中值做 pivot	避免已有序退化
小段转插入	当子数组长度 < 某阈值时用插入排序	减少递归开销
尾递归优化	先递归小的半边，大的半边用循环	保证栈深度 $O(\log n)$