快速排序

快排的思路是“定个标杆，先分堆”：随手挑一个数当基准，把比它小的都甩到左边、比它大的都甩到右边，这样这个基准就落到了它最终该在的位置。然后对左右两堆分别再快排。像整理书架，先挑一本当界，矮的往左、高的往右，两边再各自整理。

#include <iostream>
using namespace std;
void qsort(int a[], int l, int r) {
    if (l >= r) return;
    int pivot = a[l], i = l, j = r;
    while (i < j) {
        while (i < j && a[j] >= pivot) j--;
        a[i] = a[j];
        while (i < j && a[i] <= pivot) i++;
        a[j] = a[i];
    }
    a[i] = pivot;
    qsort(a, l, i - 1); qsort(a, i + 1, r);
}
int main() {
    int a[] = {3,1,4,1,5,9,2};
    qsort(a, 0, 6);
    for (int x : a) cout << x << " "; // 1 1 2 3 4 5 9
    return 0;
}

要注意别越界：递归两边时用 i-1 和 i+1，基准所在的那一格已经归位，不用再排。边界写错很容易死循环或漏排。