快速排序

重点

• 快速排序算法及其最好、最坏时间和平均时间；
• 随机快速排序算法及其期望时间；
• 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)\)。