快速排序

在基于比较的排序算法中，快速排序是目前公认最快的排序算法，平均时间复杂度为O(nlogn)。优势在于简单、就地排序、速度快，缺点是不稳定、最坏情况下会退化成平方复杂度，但可以通过一系列手段避免最坏情况的出现。

与归并排序类似，快排采用分治的思想，以整型数组从小到大排序为例，步骤如下：

1. 从待排序区间中选择一个元素作为轴(pivot)。
2. 调整数组，使得轴左边的元素均不大于它，右边的元素均大于它。
3. 对轴左右两边分别执行步骤1和2，直到区间只有一个元素为止。

选轴有不同的策略，好的轴能加快排序过程，最优情况是选区间中位数，这样调整后左右两边的元素个数接近，规模降至原来的一半。这里使用简单的策略，每次选择区间中间的元素作为轴。

void QSort(int *a, int l, int r) {
    int i = l, j = r, p = a[(l+r)/2];
    while (i <= j) {
        while (a[i] < p) i++;
        while (a[j] > p) j--;
        if (i <= j) swap(a[i++], a[j--]);
    }
    if (l < j) QSort(a, l, j);
    if (i < r) QSort(a, i, r);
}