引言

这篇文章是我在2015年写的，当时正在看算法导论中关于快排的部分，因此写下文章总结一下当时对快排的理解。这几天我一直在review一下我先前写的blog，发现有些地方写的不算太好，还有一些错误的地方。今天我重新修改一下这篇文章，把错误的地方修正过来，并补充一些新的内容。

初识Quicksort

Quicksort是一个分而治之的算法，它根据主元把一个大数组分成2个小数组：其中1个数组的元素要比主元小，另一个要比主元大。Quicksort至今依然是一个常用的排序算法，如果算法实现好的情况下，它的速度要比merge sort 和 heapsort快2到3倍。一个有效实现地Quicksort 并不是一个stable sort，即相等元素的相对顺序不能被保证。Quicksort 也可以在一个数组上进行原址排序。数学分析表明，quicksort排序n个元素平均需要 $O(n log n)$ 比较，在最坏的情况下，它需要 $O(n^2)$ 次比较，虽然这样的行为不常见。

Quicksort的步骤

Quicksort主要包含以下3步：

从数组中取出一个元素，叫做主元（pivot）
重排序数组，使得所有小于pivot的元素在它前面，所有大于pivot的元素在它后面，等于pivot的元素放在哪面都行。这样的划分以后，pivot的位置已经排好了。这个过程叫做partition操作
递归地应用步骤2到小于pivot的子数组和大于pivot的子数组

在上面的步骤中，递归的base case是数组的大小为0或1，因为这样的数组已经有序，不需要再排序。我们有很多方式来选择pivot，不同地方式会对算法的性能有很大地影响。下图是我从普林斯顿算法书的官方网站上找到的，它演示了 Quicksort 的排序过程，大家参考一下。

Quicksort

Lomuto partition scheme

由于编程珠玑和算法导论这2本很有名的书中介绍的都是这种 partition 模式，因此它被大家所熟知。这个 partition 模式选择数组中的最后一个元素作为 pivot. As this scheme is more compact and easy to understand, it is frequently used in introductory material, although it is less efficient than Hoare’s original scheme. This scheme degrades to $O(n^2)$ when the array is already in order. 关于这种模式的 pseudocode 如下：

algorithm quicksort(A, lo, hi) isif lo < hi thenp := partition(A, lo, hi)quicksort(A, lo, p - 1 )quicksort(A, p + 1, hi)algorithm partition(A, lo, hi) ispivot := A[hi]i := lo - 1    for j := lo to hi - 1 doif A[j] < pivot theni := i + 1swap A[i] with A[j]if A[hi] < A[i + 1] thenswap A[i + 1] with A[hi]return i + 1

Sorting the entire array is accomplished by quicksort(A, 0, length(A) - 1).

Hoare partition scheme

Hoare’s scheme is more efficient than Lomuto’s partition scheme because it does three times fewer swaps on average, and it creates efficient partitions even when all values are equal. Like Lomuto’s partition scheme, Hoare partitioning also causes Quicksort to degrades to $O(n^2)$ when the input array is already sorted; it also doesn’t produce a stable sort. 下面是我从算法导论中习题7-1中截取下来的 pseudocode.

Hoare partition scheme

下面我来回答一下这个习题！

关于这个 partition 的循环不变式为：

对于任意下标a， $p\le a \lt i$ , 有 $A[a]\le x$
对于任意下标b， $j\lt b \le r$ , 有 $A[b]\ge x$

1、When Hoare-Partition terminates, it returns a value j such that $p\le j \lt r$

从程序可以看出，当 while 循环开始时，j = j - 1，此时 j = r 了; 紧接着程序执行，i=i+1=p，循环终止，由于A[p] 是 pivot，所以此时A[i]=x，这就又给了j循环一次的机会，因此 $j\lt r$ . 根据循环不变式， $p\le a \lt i$ 的元素都是小于或等于x的，因此j最多到p一定会终止。

2、The indices i and j are such that we never access an element of A outside the subarray A[p … r]

在问题1中，已经证明了 $p\le j \lt r$ . 类似的逻辑，我们可以证明 $p\le i \le r$

原始版本Java实现及其性能分析

代码如下：

public static void quickSort(int[] a, int lo, int hi) {if (lo < hi) {int pivot = partition(a, lo, hi);quickSort(a, lo, pivot - 1);quickSort(a, pivot + 1, hi);}}public static int partition(int[] a, int lo, int hi) {int x = a[lo];int j = hi + 1;for (int i = hi; i > lo; i--) {if (a[i] >= x) {j--;swap(a, i, j);}}swap(a, lo, j - 1);return j - 1;}

算法时间复杂度：上面算法如果在最坏情况（数组中的元素已经有序）下，时间复杂度为Θ(n^2)；期望运行时间为Θ(nlogn)。

算法空间复杂度：由于快速排序为原址排序，所以其主要的空间复杂度来自于递归调用，每一次递归调用将在调用栈上创建一个栈帧。假设每一次传递数组的信息是采用指针的方式，那么每一次递归调用可以认为其空间复杂度为O(1)。那么算法在最坏情况下，有Θ(n)次递归调用，所以此时其空间复杂度为Θ(n)；如果算法在平均情况下，其空间复杂度为O(logn)。

随机化版本Java实现及其性能分析

代码如下：

public static int randomized_partition(int[] a, int lo, int hi) {int i = new Random().nextInt(hi - lo + 1) + lo;swap(a, lo, i);return partition(a, lo, hi);}

这个版本的实现只是对原始版本的代码稍作改动，只不过将随机在数组中选择一个主元，并与数组中的第一个元素进行交换。上述代码中的partition方法与原始版本相同。

算法时间复杂度：虽然我们对程序在最坏情况下的运行时间感兴趣，但是在随机化版本中，它并没有改变最坏情况下的运行时间，它只是减少了出现最坏情况的可能性。因此，我们只分析算法的期望运行时间，而不是其最坏运行时间。它的期望运行时间是Θ(nlogn)。

算法空间复杂度：由于这个版本的算法只是减少最坏情况出现的可能性，所以其空间复杂度与原始版本的分析一致。

Hoare版本Java实现及其性能分析

代码如下：

public static void quickSort(int[] a, int lo, int hi) {if (lo < hi) {int pivot = hoare_partition(a, lo, hi);quickSort(a, lo, pivot);quickSort(a, pivot + 1, hi);}
}public static int hoare_partition(int[] a, int lo, int hi) {int x = a[lo];int i = lo - 1;int j = hi + 1;while (true) {doj--;while (a[j] > x);doi++;while (a[i] < x);if (i < j)swap(a, i, j);elsereturn j;}
}

这个版本中的quickSort方法，第一行递归不是pivot - 1而是pivot。这是因为当hoare_partition结束时，只能保证a[p…j]中的每一个元素都小于或等于a[j+1…r]中的元素，其所选取的主元并没有就位。

这个版本的算法在含有许多重复元素的情况下，可以避免其出现最坏情况的划分。

算法时间复杂度：由于这个版本的算法并没有杜绝最坏情况的出现，所以分析同上面两个版本。

算法空间复杂度：由于这个版本的算法并没有杜绝最坏情况的出现，所以分析同上面两个版本。

通过尾递归改变最坏情况下的空间复杂度

我们知道，对于任何一种算法改进的版本来说，都不可能完全避免最坏情况的出现，它们只是减小其出现的机率。但是改变最坏情况下的空间复杂度是可能做到的。我们通过递归调用元素少的那部分，对于元素多的那部分，我们改写尾递归。只要元素少的那部分总是小于或等于输入规模的一半，那么递归调用至多为O(logn)。

代码如下：

public static void tailRecursiveQuickSort(int[] a, int lo, int hi) {while (lo < hi) {int pivot = partition(a, lo, hi);//partition方法与上述版本相同if ( pivot - lo < hi - pivot ) {quickSort(a, lo, pivot - 1);lo = pivot + 1;} else {quickSort(a, pivot + 1, hi);hi = pivot - 1;}}
}