对于包含n个数的输入数组，快速排序最坏情况时间复杂度Θ(n2)\Theta(n^2)，虽然很差，但是在实际排序中是最好的选择，因为它的平均性能是Θ(nlgn)\Theta(n\mathrm{lg}n)，而且常数因子非常小，还能进行原址排序。

快速排序的步骤

  1. 分解: 数组A[p…r]以中间元素A[q]为枢纽，分为两部分，使得前半部分的每个元素都小于等于枢纽元，枢纽元小于等于后半部分的每个元素
  2. 解决: 通过递归调用快速排序，对子数组A[p…q-1]和A[q+1…r]进行排序
  3. 合并: 因为子数组都是原址排序，所以不需要合并
1
2
3
4
5
QUICKSORT(A, p, r)
if p < r
	q = PARTITION(A, p, r)
	QUICKSORT(A, p, q-1)
	QUICKSORT(A, q+1, r)

​ 初始调用QUICKSORT(A, 1, A.length).

​ 该算法的关键在于PARTITION过程

1
2
3
4
5
6
7
8
9
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]	//如果从前向后遍历发现了比枢纽元小的元素，就换到前面，由于j保证遍历到除了枢纽元以外整个列表，因此一定可以保证所有比枢纽元小的元素都换到i之前的位置
exchange A[i+1] with A[r]	//最后再把枢纽元安置到中间
return i + 1

快速排序的性能

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

最坏情况划分 当划分的两个子问题分别为n-1和0个元素时，发生最坏情况

T(n)=T(n−1)+T(0)+Θ(n)=T(n−1)+Θ(n)T(n)=T(n-1)+T(0)+\Theta(n)=T(n-1)+\Theta(n)

用数列的方法容易得到，T(n)=Θ(n2)T(n)=\Theta(n^2).这就是说，在最坏情况下，快速排序算法的运行时间不比插入排序更好，甚至当输入数组完全有序，仍然保持平方复杂度，此时插入排序为线性复杂度。

最好情况划分 在可能的最平衡的划分中，

T(n)=2T(n/2)+Θ(n)T(n)=2T(n/2)+\Theta(n)

根据主定理可得T(n)=Θ(nlgn)T(n)=\Theta(n\mathrm{lg}n)，实际上只要是常数比例划分，时间复杂度都为O(nlgn)O(n\mathrm{lg}n)

快速排序的随机化版本 通过在子数组中随机选取一个元素作为主元实现随机抽样技术