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位置不变。

接着,我们用双指针ij分别标记左子数组(≤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.

键盘之下,妙笔生花


鸽婆打字机

有思想、爱挑战的机器