第二部分--排序和顺序统计学-第7章--快速排序
说明：该系列博客整理自《算法导论(原书第二版)》，但更偏重于实用，所以晦涩偏理论的内容未整理，请见谅。另外本人能力有限，如有问题，恳请指正！
1、综述
快速排序是一种原地排序算法，对包含 n 个数的输入数组进行排序，最坏情况运行时间为 Θ ( n2 )。虽然这个最坏情况运行时间比较差，但快速排序通常是用于排序的最佳的实用选择，这是因为其平均性能相当好：期望的运行时间为 Θ ( n lg n )，且 Θ ( n lg n )记号中隐含的常数因子很小。由于快速排序是一种原地排序，所以在虚存环境中也能很好的工作。
2、不随机快速排序（平均情况下的时间复杂度相对较高）
像合并排序一样，快速排序也是基于分治模式的。下面是对一个子数组 A [ p .. r ]快速排序的过程，符合分治过程的三个步骤：
1）、分解：数组 A [ p .. r ]被划分成两个（可能为空）子数组 A [ p .. q - 1 ]和 A [ q + 1 .. r ]，使得 A [ p .. q - 1 ]中的每一个元素都小于等于 A [ q ]，而且，A [ q ]小于等于 A [ q + 1 .. r ]中的元素。下标 q 也在这个划分过程中计算得出。
2）、解决：通过递归调用，对子数组 A [ p .. q - 1 ]和 A [ q + 1 .. r ]进行快速排序。
3）、合并：因为两个子数组是就地排序的，将它们合并不需要操作，整个数组 A [ p .. r ]已排序。
下面的过程实现了快速排序：
QUICK-SORT(A, p, r)
if p < r
q = PARTITION(A, p, r)
QUICK-SORT(A, p, q - 1)
QUICK-SORT(A, q + 1, r)
快速排序算法的关键是 PARTITION 过程，它对子数组 A [ p .. 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 总是选择 x = A [ r ]作为 主元 （pivot element），并围绕它来划分子数组。在第3行到第6行中循环的每一轮迭代开始时，对于任何数组下标 k ，有
如果 p <= k <= i ，则 A [ k ] <= x
如果 i + 1 <= k <= j - 1，则 A [ k ] > x
如果 k = r ，则 A [ k ] = x
下图总结了这一结构。过程 PARTITION 作用于子数组 A [ p .. r ]中得到四个区域。 A [ p .. i ]中的各个值都小于等于 x ， A [ i + 1 .. j - 1 ]中的值都大于 x ， A [ r ] = x 。 A [ j .. r - 1 ]中的值可以是任何值。
3、快速排序的性能
快速排序的运行时间与划分是否对称有关，而“划分是否对称”又与选择了哪一个元素来进行划分有关。如果划分是对称的，那么本算法从渐近意义上来讲，就和归并排序算法一样快；如果划分是不对称的，那么本算法渐近上就和插入排序一样慢。下面我们讨论划分为对称和不对称时快速排序的性能。
1）、最坏情况划分
快速排序的最坏情况划分发生在划分过程产生的两个区域分别包含 n - 1个元素和1个0元素的时候。假设算法的每一次递归调用都出现了这种不对称划分。划分的时间代价为 Θ ( n )。对一个大小为0的数组进行递归调用后，返回 T ( 0 ) = Θ ( 1 )，故算法的运行时间为 T ( n ) = T ( n - 1 ) + Θ ( n )。
从直观上看，如果将每一层递归的代价加起来，就可以得到一个算术级数，其和值的量级为Θ ( n2 )。利用代换法，可以比较直接的证明递归式T ( n ) = T ( n - 1 ) + Θ ( n )的解为T ( n ) = Θ ( n2 )。
因此，如果在算法的每一层上递归上，划分都是最大程度不对称，那么算法的运行时间就是Θ ( n2 )。即，快速排序算法的最坏情况运行时间并不比插入排序好。此外，当输入数组已经完全排好序时，快速排序的运行时间为Θ ( n2 )，而在同样情况下，插入排序的运行时间为Θ (n)。
2）、最佳情况划分
在 PARTITION 过程可能的最平衡划分中，得到的两个子问题的大小都不可能大于n/2，因为其中一个子问题的大小为 FLOOR（n / 2） ，另一个子问题的大小为 CEIL(n / 2) - 1。这种情况下，其运行时间的递归式为 T ( n ) <= 2 T ( n / 2 ) + Θ ( n )。该递归式的解为 T ( n ) = O ( n lg n )。由于在每一层的递归上，划分的两边都是对称的，因此，从渐近意义上来看，算法运行的就跟快了。
3）、平衡的划分
快速排序的平均情况运行时间与其最佳情况运行时间很接近，而不是非常接近于其最坏情况运行时间。要理解这一点，就要理解划分的平衡性是如何在刻画运行时间的递归式中反映出来的。
当好、坏划分交替分布在各层时，快速排序的运行时间和最佳情况划分是一样的，即O ( n lg n )，只是O记号中隐含的常数因子要略大一些。如何好坏交替呢？需要随机的选取选择 x 作为 主元 （pivot element），而不是像不随机快速排序那样 x 一直等于 A [ r ]。随机快速排序在下面讲解。
4、随机快速排序
在探讨快速排序的平均性态过程中，我们已经假定输入数据的所有排列都是等可能的，但在工程中，这个假设并不是总是成立的。所以，我们需要向算法中加入随机化的成分，以便于对于所有输入均能获得很好的平局情况性能。
随机划分使用 随机取样 （random sampling）的随机化技术，从子数组 A [ p .. r ]中随机选择一个元素并与 A [ r ]互换，因为主元是随机选择的，我们期望在平均情况下，对输入数组的划分能够比较对称。
RANDOMIZED-PARTITION(A, p, r)
i = RANDOM(p, r)
exchange A[r] with A[i]
return PARTITION(A, p, r)
RANDOMIZED-QUICK-SORT(A, p, r)
if p < r
q = RANDOMIZED-PARTITION(A, p, r)
RANDOMIZED-QUICK-SORT(A, p, q - 1)
RANDOMIZED-QUICK-SORT(A, q + 1, r)
5、参考
