算法1

快速排序算法可以分为三个步骤：

1. 选取pivot
2. 划分，根据选取的pivot将数组划分成小于pivot的部分和大于pivot的部分
3. 递归求解小于pivot和大于pivot的部分

一种比较简单的划分方式为 Lomuto Partition Scheme，这种划分方式是单向划分，我们选取数组最左边的元素q[l]作为pivot，之后从左到右扫描数组，将数组划分为小于pivot和大于等于pivot两部分，之后需要将pivot交换到它对应的位置，注意这一步不能忽略，不然q[l]永远都不会被移动。最后我们对划分好的子数组进行递归求解。这种划分方式保证了划分完后q[j]就是第j - l + 1大的数。

时间复杂度

这种划分方式在平均情况下时间复杂度为 $O(n\log n)$，空间复杂度为 $O(\log n)$。最坏情况为数组已排好序或者数组中的数都相等，此时每次划分只会将数组的长度减少1，会递归 $n$ 次，导致时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。

C++代码

void quick_sort(int q[], int l, int r) {
    if (l >= r) return;

    int x = q[l], j = l;
    for (int i = l + 1; i <= r; i ++ ) 
        if (q[i] < x) swap(q[ ++ j], q[i]);

    swap(q[l], q[j]);
    quick_sort(q, l, j - 1);
    quick_sort(q, j + 1, r);
}

思考题

这里能否对代码进行改动使得它将数组划分成小于等于pivot和大于pivot的两部分，这样划分是否会影响正确性？

算法2

y总的模板，这种方式会将数组划分为小于等于和大于等于pivot 的左右两部分，并且每一部分都不会为空，因为每次递归的时候数组的长度都会变小从而确保不会死循环。如果每次都选取数组最左边的元素来作为pivot，当数组已经是有序的时候每次递归数组的长度只会减少一，导致时间复杂度变为 $O(n^2)$，这可以通过选中间元素作为pivot或者每次随机选取数组中一个元素与最左边的元素交换来解决。注意这里不能用最右边的元素作为pivot，这样如果数组最右边是最大元素的话会导致划分完[l, j]不变导致死循环。

由于划分完成后pivot不一定在这两部分的分界线上，所以在做比如得到第k大的数这种题目时不能用j - l + 1 == k来判断q[j]为第k大的数，因为左半区间只保证了所有数小于等于 pivot，而不一定都小于等于q[j]。

另外值得一提的是这种双向划分方式就是 Hoare 在最开始的论文中提出的方式 – Hoare Partition Scheme。

时间复杂度

平均时间复杂度 $O(n\log n)$，最坏情况下 $O(n^2)$，在数组已排好序的情况下出现，可以通过随机化或者取中点来避免最差情况。

C++ 代码

void quick_sort(int q[], int l, int r) {
    if (l >= r) return;

    int x = q[l + r >> 1], i = l - 1, j = r + 1; 
    while (i < j) {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

思考题

能否对代码进行改动使得它不使用do while循环与++操作符并保证其正确性？

算法3

将算法改成尾递归，可以使空间严格小于 $O(\log n)$，具体思想是把第一次递归调用改成永远先选长度较小的那一半，第二次递归调用改成循环（即尾递归）。这样由于每次都选较小的那一半，所以每次递归长度至少变小一半，递归栈不会超过 $O(\log n)$。

C++ 代码

void quick_sort(int q[], int l, int r)
{
    // 将第二次递归改为循环
    while (l < r) {
        int p = partition(q, l, r);
        // 先递归较短的部分,可以把空间优化到O(logn)
        if (p - l < r - p) {
            quick_sort(q, l, p - 1);
            l = p + 1;
        } else {
            quick_sort(q, p + 1, r);
            r = p - 1;
        }
    }
}

附：思考题解答

1. 可以，将判断条件由q[i] < x改成q[i] <= x即可。
2. 可以，这里附上一份参考代码：

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int x = q[l + r >> 1], i = l,  j = r;
    while (1) {
        while (q[i] < x) i = i + 1;
        while (q[j] > x) j = j - 1;
        if (i >= j) break;
        swap(q[i], q[j]);
        i = i + 1;
        j = j - 1;
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}