算法描述

与归并排序一样，快速排序也使用了分治思想。以对子数组A[p..r]进行快速排序为例：

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

QUICKSORT(A, p, r)
if p < r
  q = PARTITION(A, p, r)
  QUICKSORT(A, p, q-1)
  QUICKSORT(A, q+1, r)

PARTITION(A, p, r)
x = A[r]
i = p - 1
for j = p to r - 1
  if A[j] <= x
    i = i + 1
    exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i + 1

PARTITION示例

算法特性：

最坏情形运行时间：T(n) = T(n-1) + Θ(n) = Θ(n²)。
最好情形运行时间：T(n) = 2T(n/2) + Θ(n) = Θ(nlgn)。

快速排序的随机化版本

通过显式地对输入进行重新排序，使得算法实现随机化。但是，如果使用一种称为随机抽样的随机化技术，那么可以使得分析变得更加简单。随机抽样是从子数组A[p..r]中随机选择一个元素作为主元，而不是采用A[r]作为主元。为此，首先将A[r]与从A[p..r]中随机选择的一个元素交换。通过对序列p,...,r的随机抽样，我们可以保证主元元素x=A[r]是等概率地从子数组的r-p+1个元素中选取的。因为主元元素是随机选取的，我们期望在平均情况下，对输入数组的划分是比较均衡的。

RANDOMIZED-PARTITION(A, p, r)
i = RANDOM(p, r)
exchange A[r] with A[i]
return PARTITION(A, p, r)

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)