快速排序

快速排序是另一种基于分治技术的重要排序算法。合并排序是按照元素在数组中的位置对它们进行划分，快速排序按照元素的值对它们进行划分。具体来说，它对给定数组中的元素进行重新排列，以得到一个快速排序的分区。在一个分区中，所有在s下标前的元素都小于等于A[s],所有在s下标之后的元素都大于等于A[s].

建立一个分区以后，A[s]已经位于它在有序数组中的最终位置，接下来我们继续对A[s]前和A[s]后的子数组分别使用同样方法进行排序.

算法 Quicksort(A[l..r])
    //用Quicksort对子数组排序
    //输入：数组A[0..n-1]中的子数组A[l..r],由左右下标l和r定义。
    //输出：非降序排序的子数组A[l..r]
    if l < r
        s <- Partition(A[l..r]//s是分裂点
        Quicksort(A[l..s-l])
        Quicksort(A[s+1..r])

下面使用这个算法得到数组A[0..n-1]的一个分区。首先，我们要选择一个元素，接下来会根据该元素的值来划分子数组。该元素为中轴.选择中轴有许多不同的策略。现在我们只使用最简单的策略——选择子数组的第一个元素：p=A[l].

建立一个分区，我们使用一种基于两次扫描子数组的高效方法：一次是从左到右，另一次是从右到左，每次都把子数组的元素和中轴进行比较。从左到右的扫描从第二个元素开始，扫描会忽略小于中轴的元素，直到遇到第一个大于等于中轴的元素才停止。从右到左的扫描会从最后一个元素开始，扫描会忽略大于中轴的元素，直到遇到第一个小于等于中轴的元素才会停止。

扫描的指针是否相交，会发生3种不同的情况。如果扫描指针i和j不相交，也就是说i < j,我们简单地交换A[i]和A[j]，再分别对i加一，j减一，然后继续开始扫描。

如果扫描指针相交，也就是说i > j,把中轴和A[j]交换以后，我们得到了该数组的一个分区。

最后，如果扫描指针指向的是同一个元素，也就是说i=j,被指向元素的值一定等于p。

我们将第三种情况和指针相交的情况结合起来，只要i≧j，就交换中轴和A[j]的位置。

下面这段伪代码实现了分区的过程。

算法 Paritition(A[l..r])
    //以第一个元素为中轴，对子数组进行分区
    //输入：数组A[0..n-1]中的子数组A[l..r]，由左右下标l和r定义
    //输出：A[l..r]的一个分区，分裂点的位置作为函数的返回值
    p <- A[l]
    i <- l; j <- r+1
    repeat
        repeat i <- i+1 until A[i] ≧ p
        repeat j <- j-1 until A[j] ≦ p
            swap(A[i], A[j])
    until i ≧ j
    swap(A[i], A[j])    //当i≧j撤销最后一次交换
    swap(A[l], A[j])
    return j

我们注意：如果扫描指针交叉了，建立分区之前所执行的键值比较次数是n+1;如果它们相等，则是n。最优情况，所有的分裂点位于相应子数组的中点。再最有情况下，键值比较的次数Cbest(n)满足下面的递推式：

根据主定理，Cbest(n)∈Θ(nlog2 n)；对于n＝2^k的情况求得Cbest(n)＝nlog2 n.

在最差的情况下，发生在增序的数组上，如果A[0..n-1]是严格递增的数组，我们将A[0]作为中轴，从左到右的扫描会停在A[1]上，而从右到左的扫描会一直处理到A[0]为止，导致分裂点出现在0这个位置，即A[0]和它本身进行了交换（进行了n＋1吃比较之后建立了分区）然后快速排序算法还会对严格递增的数组A[1..n-1]进行排序。排序一直继续到最后一个子数组A[n-2..n-1].这种情况下，键值比较的总次数应该等于：

现在，轮到讨论快速排序在平均情况下的效率了。快速排序的平均键值比较次数记为Cavg(n)。假设分区的分裂点s位于每个位置的概率都是1/n，我们得到下面的递推关系式：

因此，快速排序在平均情况下，仅比最优情况多执行38%的比较操作。此外，它的最内层的循环效率非常高，使得在处理随即排列的数组时，速度要比合并排序快（对于堆排序也是如此。堆排序是另一种效率为nlogn的算法，我们会在第6章对它进行讨论）。

更好的中轴选择方法:三平均分区法 它以数组最左边，最右边和最中间的元素的中值作为中轴.

应该指出，分区思想的作用不仅仅局限于排序问题。比如说，我们会在5.6节讨论一个饿关于选择问题的快速算法，分区思想在其中起到了很大的作用。