第7章-快速排序

发表于 | 分类于
字数统计: 965 | 阅读时长 ≈ 3

快速排序

快速排序是一种最坏情况时间复杂度为 $\Theta(n^2)$ 的排序算法，但是快速排序在实际排序应用中通常是最好的选择，因为它的平均性能非常好，期望时间复杂度是 $\Theta(n\lg n) $。

快速排序的描述

快速排序使用了分治思想：

  • 分解：数组 $A[p .. r]$ 被划分为两个（可能为空）子数组 $A[p..q-1]$ 和 $A[q+1..r]$，使得 $A[p..q-1]$ 中的每一个元素都小于等于 $A[q]$，而 $A[q]$ 也小于等于 $A[q+1.. r]$ 中的每个元素。其中计算下标 $q$ 也是划分过程的一部分。
  • 解决：通过递归调用快速排序，对两个子数组进行排序。
  • 合并：因为子数组都是原址排序的，所以不需要合并操作。

稳定排序：在排序算法中，相同值的两个元素，在输入数组中先出现的数在输出数组中也先出现。例如：冒泡排序，插入排序，基数排序，归并排序。

原址排序：基本上不需要额外辅助的空间，允许少量额外的辅助变量的排序。如选择排序，插入排序，希尔排序，快速排序，堆排序。而归并排序，计数排序，基数排序不是原址排序。

下面的程序实现快速排序：

1
2
3
4
5
def QUICKSORT(A, p, r):
    if p < r :
        q = PARTITION(A, p, r)
        QUICKSORT(A, p, q-1)
        QUICKSORT(A, q+1, r)

数组的划分

算法的关键部分是 PARTITION 过程，它实现了对子数组的原址重排。

1
2
3
4
5
6
7
8
9
def PARTITION(A, p, r):
    x = A[r]	# 选定 x = A[r] 作为主元
    i = p - 1
    for j in range(p, r-1):
        if A[j] <= x:
            i = i + 1
            swap(A[i], A[j])
     swap(A[i+1], A[r])
    return i + 1

PARTITION 在子数组 $A[p..r]$ 上的时间复杂度为 $\Theta(n) $ 其中，$n = r-p+1$。

快速排序的性能

快速排序的运行时间依赖于划分是否平衡，而平衡与否又依赖于用于划分的元素。如果划分是平衡的，那么快速排序的性能与归并排序一样。如果划分是不平衡的，那么快速排序的性能就接近插入排序了。

最坏情况划分

当划分产生两个子问题分别包含了 $n-1$ 个元素和 0 个元素时，快速排序的最坏情况发生。此时算法的运行时间为：

因此可以得到，此时快速排序的时间复杂度为 $\Theta(n^2)$。

最好情况划分

当划分产生两个子问题分别包含了 $n/2$ 个元素和 $n/2 $ 个元素时，快速排序的最好情况发生。此时算法的运行时间为：

因此可以得到，此时快速排序的时间复杂度为 $\Theta(n \lg n )$。

快速排序的随机化版本

我们可以通过在算法中引入随机性，从而使算法对所有的输入都能获得较好的期望性能。

随机化的快速排序对原始快速排序改动很小，只需要从将 $A[r]$ 作为主元改变为从随机一元素作为主元即可：

1
2
3
4
5
6
7
8
9
10
def RANDOMIZED_QUICKSORT(A, p, r):
    if p < r:
        q = RANDOMIZED_PARTITION(A, p, r)
        RANDOMIZED_QUICKSORT(A, p, q-1)
        RANDOMIZED_QUICKSORT(A, q+1, r)
        
def RANDOMIZED_PARTITION(A, p, r):
    i = RANDOM(p, r)
    swap(A[r], A[i])
    return PARTITION(A, p, r)

期望为线性时间的选择算法

利用上述 PARTITION/RANDOMIZED_PARTITION 过程，寻找数组中第 $i$ 小的元素，时间复杂度只需 $\Theta(n) $。

1
2
3
4
5
6
7
8
9
10
11
def RANDOMIZED_SELECT(A, p, r, i):
    if p == r:
        return A[p]
    q = RANDOMIZED_PARTITION(A, p, r)
    k = q - p + 1
    if i == k:
        return A[q]
    else if i < k:
        return RANDOMIZED_SELECT(A, p, q-1, i)
    else:
        return RANDOMIZED_SELECT(A, q+1, r, i-k)