快速排序

重点

• 快速排序算法及其最好、最坏时间和平均时间；
• 随机快速排序算法及其期望时间；
• Partition 算法；
• 几个排序算法的比较：插入排序、归并排序、堆排序和快速排序

快速排序算法利用了分治法的思想，是一种非常巧妙的算法。其最坏时间复杂度为 $\Theta(n^2)$，期望时间复杂度为 $\Theta(n\lg n)$，且其中的常数因子非常小，另外，快速排序算法是一种原址排序。

基本思想

快速排序递归地将问题划分成两部分，然后分别解决，具体地，其分支策略如下：

• 分解：数组 A[p...r] 被划分成两个子数组 A[p...q - 1] 和 A[q + 1...r]，使得前者中的每一个元素都小于等于 A[q] 后者的每一个元素都大于等于 A[q]；
• 解决：通过递归调用快速排序，堆子数组进行排序；
• 合并：无需合并。

因此快速排序算法的代码可以总结如下：

def QuickSort(A, p, r):
    if p < r:
        q = Partition(A, p, r)
        QuickSort(A, p, q - 1)
        QuickSort(A, q + 1, r)

显然其关键在于对数组的划分，即 Partition 算法。

数组的划分

划分数组的 Partition 算法是快速排序的灵魂，实现了对数组的原址排序。算法的关键是两个位置指针 $i, j$，其中 $j$ 作为一个递增的指针对数组进行遍历，$i$ 则指示着较小的那个子数组（一般是左侧）的最后一个位置。

具体地，令 $j$ 从 $0$ 开始递增，且比较 A[j] 和数组的最后一个元素（被称为划分的主元素）即 A[r]，如果 A[j] 小于等于 A[r]，则将 A[j] 换到左侧较小的子数组中去，同时更新指针 $i$ 使其满足性质。

如此对整个数组遍历一次，使得数组除了最后一个元素外，之前的每一个元素都以最后一个元素为分界，排列在位置 $i + 1$ 的两侧，因此最后只需要交换 A[r] 和 A[i + 1] 并返回 $i + 1$ 即可完成划分操作。

def Partition(A, p, r):
    i = p - 1
    for j in range(p, r):
        if A[j] <= A[r]:
            i += 1 # 时刻保证 i 指向左侧子数组的最后一个位置
            A[i], A[j] = A[j], A[i] # 将小于最后一个元素的数交换到左侧子数组的位置
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1

利用下面的循环不变量可以证明算法的正确性：

循环不变量

在算法 3 至 6 行循环体的每一轮迭代开始时，对任意数组下标 $k$，有：

• 若 $p \leqslant k \leqslant i$，则 $A[k] \leqslant A[r]$；
• 若 $i + 1 \leqslant k \leqslant j - 1$，则 $A[k] > A[r]$；
• 若 $k = r$，则 $A[k] = A[r]$。

具体证明本文不再赘述。划分算法对数组进行一次遍历，因此其时间复杂度为 $\Theta(n)$。

快速排序的性能

快速排序算法的性能与划分操作结果是否平衡有关，也即与用来划分的主元素有关。如果划分平衡，则快速排序算法的性能与归并排序一样，如果划分不平衡，那么快速排序的性能就接近于插入排序了。

最坏情况划分

划分的最坏情况发生在两个数组的大小分别为 $0$ 和 $n - 1$ 时，不妨设每次划分都是这样的情况，则算法的递归式为

$$T(n) = T(n - 1) + T(0) + \Theta(n) = T(n - 1) + \Theta(n)$$

将每一层的结果累加得到 $T(n) = \Theta(n^2)$。

最好情况划分

在最平衡的情况下，划分的两个子数组的大小都近似为 $n / 2$，不妨设每次划分都是这样的情况，则算法的递归式为

$$T(n) = 2T(n / 2) + \Theta(n)$$

利用主定理 $n^{\log_2 2} = \Theta(n)$ 因此算法的复杂度为 $\Theta(n\lg n)$。

期望的划分情况

快速排序的平均运行时间更接近于其最好情况，而非最坏情况。可以考虑每次划分都是 $9 : 1$ 这样看起来非常不均衡的划分：设递归深度为 $h$，则有

$$n \cdot \left( \frac{9}{10} \right)^h = 1 \implies h = \log_{10/9} n = \Theta(\lg n)$$

每层的代价为 $cn$，因此总代价为 $\Theta(n\lg n)$，接近于最好情况。事实上，即使是 $99:1$ 这样的划分也一样，因此只要划分是常数比例的，算法的运行时间总是 $\Theta(n\lg n)$。

快速排序的随机化版本

通过上面的分析我们知道，快速排序的性能取决于划分的子集是否平衡，因此可以考虑引入随机抽样来使得划分尽可能平衡。我们在 Partition 算法中加入一步随机抽样选择主元素，实现随机化快速排序。

def RandomizedPartition(A, p, r):
    i = random.randint(p, r)
    A[r], A[i] = A[i], A[r]
    return Partition(A, p, r)

def RandomizedQuickSort(A, p, r):
    if p < r:
        q = RandomizedPartition(A, p, r)
        RandomizedQuickSort(A, p, q - 1)
        RandomizedQuickSort(A, q + 1, r)

在输入元素互异的情况下，使用 RandomizedPartition 的快速排序算法的期望运行时间为 $O(n\lg n)$。