快速排序

这里介绍的快速排序与绝大部分《数据结构》教材上的并不完全一样（但是算法思想差不多，并且算法效率没有差异），笔者觉得下面这个快速排序在写法上要优雅得多，更推荐使用。

快速排序基于分治思想，

(1)选择一个轴值x；

(2)将序列划分为两部分，左半序列所有元素全 $\leqslant$ x，右半序列所有元素全 $\geqslant$ x；

(3)递归处理左半序列和右半序列。

void QuickSort(int a[], int l, int r) {
    if (l >= r) return;

    int i = l-1, j = r+1, x = a[(l+r)/2];

    while (i < j) {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }

    QuickSort(a, l, j);
    QuickSort(a, j+1, r);
}

注解：

(1)也可用i作划分边界：

void QuickSort(int a[], int l, int r) {
    if (l >= r) return;

    int i = l-1, j = r+1, x = a[(l+r+1)/2];

    while (i < j) {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }

    QuickSort(a, l, i-1);
    QuickSort(a, i, r);
}

(2)若用j作划分边界，轴值x一定不能取到a[r]，可以写x = a[l]、x = a[(l+r)/2]等；若用i作划分边界，轴值x一定不能取到a[l]，可以写x = a[r]、x = a[(l+r+1)/2]等。

(3)写成x = a[(l+r)/2]与写成x = a[l]相比，可以避免在序列原本就有序的情况下，快排复杂度退化为$O(n^2)$；随机选择轴值也能避免出现复杂度$O(n^2)$的情况，但是要排除掉轴值x为a[r]。

---