『算法导论』第 7 章：快速排序

快速排序通常是实际 排序 应用中最好的选择。它在最坏情况下的时间复杂度很差，但是平均性能非常好。另外，它能够进行原址排序。

快速排序的描述

与归并排序一样，快速排序也用到了分治思想。其主过程的代码如下：

void quicksort(int A[], int p, int r)
{
    if (p < r) {
        int q = partition(A, p, r);
        quicksort(A, p, q-1);
        quicksort(A, q+1, r);
    }
}

算法的关键是数组划分过程PARTITION，它实现了对子数组$A[p…r]$的原址重排。选择$x=A[r]$作为主元，围绕它来划分数组$A[p…r]$。完成划分后，$A[p…q-1]$的每一个元素都小于等于$A[q]$，而$A[q]$也小于等于$A[q+1…r]$中的每个元素。程序最后返回主元的新小标。代码如下：

void Exch(int *arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

int partition(int A[], int p, int r)
{
    int x = A[r];
    int i = p - 1;
    for (int j = p; j < r; j++) {
        if (A[j] <= x) {
            ++i;
            Exch(A, i, j);
        }
    }
    Exch(A, i+1, r);
    
    return (i + 1);
}

PARTITION在子数组$A[p…r]$上的复杂度为$\Theta(n)$，其中$n=r-p+1$。

快速排序的性能

当划分产生的两个子问题分别包含了$n-1$个元素和$0$个元素时，快速排序的 最坏情况 就发生了。假设算法的每一次递归调用中都出现了这种不平衡划分，可以得到如下的递归式：

$$

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

$$

可以得到时间复杂度为$T(n) = \Theta(n^2)$，也就是说，最坏情况下，快速排序的运行时间并不比插入排序好。当输入数组已经完全有序时，快速排序的时间复杂度为$\Theta(n^2)$，而这种情况下插入排序的时间复杂度为$O(n)$。

在可能的最平衡的划分中，PARTITION得到的两个子问题的规模都不大于$n/2$，这便是快速排序的 最好情况 。运行时间的递归式为：

$$

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

$$

上述递归式的解为$T(n) = \Theta(n \lg n)$，通过在每一层递归中都平衡划分子数组，我们得到了渐近时间上更快的算法。

实际上，只要划分是常数比例的，算法的运行时间总是$O(n \lg n)$，即使是$99:1$的划分，其时间复杂度仍然是$O(n \lg n)$。当对一个随机输入的数组进行快速排序时，平均情况下，划分同时混合有“好”和“差”的划分。当好和差的划分交替出现时，快速排序的复杂度和全是好的划分时一样，仍然是$O(n \lg n)$，区别只在于隐含的常数因子要略大一些。

快速排序的随机化版本

前面的讨论基于一个前提：输入数据的所有排列都是等概率的。实际工程中并不总是这样的，所以我们可以通过在算法中引入随机性，从而使得算法对于所有的输入都能获得较好的期望性能。

可以从子数组$A[p…r]$中随机选择一个元素作为主元，这通过将$A[r]$与从$A[p…r]$中随机选出的一个元素交换来实现。由于主元元素是随机选取的，在平均情况下，对数组的划分是比较均衡的。代码略。

快速排序分析

本节用严格的数学推导计算了快速 排序算法 的运行时间。在输入元素互异的情况下，随机化版本的期望运行时间为$O(n \lg n)$。