快速排序

快速排序也是分治，但把功夫下在「分」上：选一个基准值 pivot，把比它小的甩到左边、大的甩到右边（一次 partition），基准就落到最终位置；然后左右两段各自再快排。

void quick_sort(int a[], int l, int r) {
    if (l >= r) return;
    int i = l, j = r, pivot = a[(l + r) / 2];
    while (i <= j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) swap(a[i++], a[j--]);
    }
    quick_sort(a, l, j);      // 递归左半
    quick_sort(a, i, r);      // 递归右半
}

平均复杂度 $O(n\log n)$，常数小、实测快；但最坏（基准每次都取到极值、或数据已近乎有序）会退化到 $O(n^2)$。快排是不稳定排序，归并才稳定。

考试常见坑：（1）基准取端点时遇到有序数据会退化，取中间或随机基准更稳；（2）while 内外的 <=、<、> 边界很容易写错导致死循环，务必背准这套模板；（3）竞赛直接用 sort 即可（内省排序，避开了最坏情况），手写主要用于理解和面试。