快速排序最坏情况下的时间复杂度是$\Theta(n^2)$，但是它的期望时间复杂度是$\Theta(nlogn)$，而且隐含的常数因子非常小。

今天的文章复习一下快排的原理和尝试着自己实现一下代码。

大体思路

快排的大体思路是：将一个数组A[p..r]划分成子数组A[p..q-1]和A[q+1..r]，使得前半部分都比q大，后半部分都比q小。这样的话在整体上这三部分就是有序的。再在每个子数组上重新进行这个过程，直到子数组只有一个元素或为空的时候，排序就完成了。

基本代码实现

取子数组第一个值为比较值(当然…算法导论上是最后一个值，其实个人感觉没大差)，索引j分割当前子数组，索引j左边的都是小于比较值的数，右边的都是大于比较值的数。

def QuickSort(p, r):
    if (p >= r):
        return;  # 只有一个元素,不需要再排序

    q = A[p];  # 取第一个数字为比较变量
    j = p;  # 索引j从第二个数字开始
    for i in range(p + 1, r + 1):
        if (A[i] < q):
            j = j + 1;
            swap(i, j);  # j自增，并将边界右边的大值和当前的小值交换位置。
    swap(p, j);  # 最后将比较标量和边界的小值交换，整体完成有序(数组1，q，数组2)
    QuickSort(p, j - 1);
    QuickSort(j + 1, r);


def swap(a, b):
    tmp = A[a];
    A[a] = A[b];
    A[b] = tmp;

一些优化

1. 对于已经大致有序的数组，取第一个(或最后一个)元素作为比较值可能会导致快排退化到$\Theta(n^2)$的复杂度，所以可以考虑在当前子数组中随机选取比较值。
2. 当子数组分割到比较小的时候，可以使用插入排序来代替快排，这样可以一定程度上提高运算速度。

P.S.以上两点都是从《算法导论》上看到的，在不同的环境下一定会有不同的优化方法，国情不同，处理方式不同…