vlambda博客
学习文章列表

Computer science is no more about computers than astronomy is about telescopes.

在上文「」中，我们发现插入排序与合并排序各有优劣：前者是原地进行，但时间复杂度高；后者效率更快，但要占用额外空间。在本文中，我们将探究快速排序（quicksort）是如何发挥多项优势，做到期望运行时间为 ，且能够实现原地排序的 (sort in place) 的。

原理与实现

与合并排序相似，快速排序也采用了分而治之的模式：(1) Divide：选定数组中的一个元素作为pivot，将数组 划分 (partition) 为两个子数组，使得左边的每个元素小于pivot，右边的每个元素大于pivot；(2) Conquer：然后对两个子数组分别调用快速排序；(3) Combine：如此递归地进行数组划分和子数组排序后，无需combine操作，即可得到排序后的完整数组。

有了以上思路，我们可以先写出QuickSort函数（注意先判断序列长度大于1）：

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

对比合并排序的“递归合并”，快速排序的关键在于“递归划分”。

Merge sort: recursively merging

Quicksort: recursively partitioning

下面我们来编写Partition函数，实现数组 A[p:r] 的原地重排：

首先，如何选取pivot呢？经典的方法是设定pivot为x=A[r-1]，也就是数组的最后一个元素（也可以设定为第一个元素），这样做的好处是保持pivot位置不变。

接着，我们用双指针i和j分别标记左子数组（≤x）和右子数组（≥x）的右边界。指针j不断向前移动，一旦A[j]<=x就将A[j]与A[i+1]交换，使A[j]加入左子数组，同时指针i向前移动一格。指针j移动到r-2的位置时，完成子数组划分。

最后，交换A[i+1]和A[r-1]，使pivot处于两个子数组中间，并标记其位置i+1。

def exchange(A, i, j):
 m = A[i]
 A[i] = A[j]
 A[j] = m

def Partition(A, p, r):
 x = A[r-1]
 i = p-1
 for j in range(p, r-1):
  if A[j] <= x:
   i += 1
   if i < j:
    exchange(A, i, j)
 exchange(A, i+1, r-1)
 return i+1

以下是完整的快速排序的Python实现：

def exchange(A, i, j):
 m = A[i]
 A[i] = A[j]
 A[j] = m

def Partition(A, p, r):
 x = A[r-1]
 i = p-1
 for j in range(p, r-1):
  if A[j] <= x:
   i += 1
   if i < j:
    exchange(A, i, j)
 exchange(A, i+1, r-1)
 return i+1

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

性能分析

最坏情况

由于Partition的运行时间为 ，如果每次划分都是最大程度的不对称，即所有元素都被划分到一个子数组，另一个子数组为空，则QuickSort的运行时间可以递归地表示为：

解得 ，也就是当输入数组已经排好序时，快速排序反而效率最低，运行时间为 。

最佳情况

如果每次划分都是均衡的，即两个子数组各包含一半元素，则运行时间的递推公式为：

解得 ，与合并排序的运行速度相当。

随机化快速排序

为了不受输入数组的排序程度的影响，我们可以随机选取A[p:r]中任一元素作为pivot，而不是始终选用A[r-1]。这样简单改动后，就能使数组的划分在平均情况下比较对称。

def RandomizedPartition(A, p, r):
 i = random.randrange(p, r)
 exchange(A, i, r-1)
 return Partition(A, p, r)

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

对于所有输入，随机化快速排序的期望运行时间是 ，证明见MIT算法导论课P4。因此，很多情况下，随机化快速排序是面对大量输入数据时的理想选择。

参考文献：

Cormen, T. H., et al. (2009). Introduction to algorithms. MIT press.