快速排序—算法导论(8)

2015年09月21日 21:00

1. 算法描述

快速排序(quick-sort) 与前面介绍的归并排序(merge-sort) 一样，使用了分治思想。

下面是对一个一般的子数组A[p~r]进行快速排序的分治步骤：

1. 分解：数组A[p~r]被划分为两个子数组A[p ~ q]和A[q+1 ~ r]，使得A[q]大于等于A[p ~ q]中的每个元素，且小于等于A[q+1 ~ r]中的每个元素。（需要说明的是，我们允许A[p ~ q]和A[q+1 ~ r]为空）

2. 解决：对子数组A[p ~ q]和A[q+1 ~ r]递归的调用快速排序。

3. 合并：因为子数组都是原址排序的，所以不需要合并操作，此时的A数组已经是排好序的。

下面给出伪代码：

可以看出，算法的关键是partiton方法的实现。下面给出它的算法实现：

直接看可能觉得很晕，我们结合实例看看它是如何工作的：

上图表示的是对子数组$A[p~r] =[2,8,7,1,3,5,6,4]$进行排序时，每次迭代之前数组元素和一些变量的值。

我们可以初步看出，在i和j移动的过程中，数组被分成了三个部分（分别用灰色，黑色，白色表示），其中i和j就是分割线，并且浅灰部分的元素均比A[r]小，黑色部分的元素均比A[r]大（(i)图除外，因为循环完毕之后执行了exchange A[i+1] with A[j]）。

我们再仔细分析一下具体细节：

1. 首先看迭代之前的部分。它执行了x = A[r]，目的是把子数组A的最后一位作为一个“基准”，其他的所有元素都是和它进行比较。它在迭代过程中值一直都没改变。然后执行i = p –基准 1，此时i在子数组A的左端。
2. 再看迭代部分。迭代时j从子数组A的开头逐步移至A的倒数第二位。每次迭代中，会比较当前j位置的值和“基准”的大小，如果小于或相等“基准”，就将灰色部分的长度增加1（i=i+1），然后把j位置的值置换到灰色部分的末尾（exchange A[i] with A[j]）。这样迭代下来，就能保证灰色部分的值都比“基准”小或相等，而黑色部分的值都比“基准”大。
3. 最后看迭代完成后的部分。就进行了一步 exchange A[i+1] with A[j]操作，就是把“基准”置换到灰色部分与黑色部分之间的位置。 这样所有的操作下来，就产生了一个“临界”位置q，使得A[q]大于等于A[p ~ q]中的每个元素，而小于等于A[q+1 ~ r]中的每个元素。 更严格的，我们可以用以前介绍的循环不变式来证明其正确性。但由于叙述起来比较麻烦，这里就不给出了。

下面我们给出 快速排序 算法的 Java 实现代码：

public static void main(String[] args) {
    int[] array = { 9, 2, 4, 0, 4, 1, 3, 5 };
    quickSort(array, 0, array.length - 1);
    printArray(array);
}

/**
 * 快速排序
 *
 * @param array 待排序数组
 * @param start 待排序子数组的起始索引
 * @param end 待排序子数组的结束索引
 */
public static void quickSort(int[] array, int start, int end) {
    if (start < end) {
        int position = partition(array, start, end);
        quickSort(array, start, position - 1);
        quickSort(array, position + 1, end);
    }
}

/**
 * 重排array，并找出“临界”位置的索引
 *
 * @param array 待重排数组
 * @param start 待重排子数组的起始索引
 * @param end 待重排子数组的结束索引
 */
public static int partition(int[] array, int start, int end) {
    int position = start - 1;
    int base = array[end];
    for (int i = start; i < end; i++) {
        if (array[i] <= base) {
            position++;
            int temp = array[position];
            array[position] = array[i];
            array[i] = temp;
        }
    }
    int temp = array[position + 1];
    array[position + 1] = array[end];
    array[end] = temp;
    return position + 1;
}

/**
 * 打印数组
 */
public static void printArray(int[] array) {
    for (int i : array) {
        System.out.print(i + "");
    }
    System.out.println();
}

2. 算法分析1

快速排序的运行时间是跟划分密切相关的，因为划分影响着子问题的规模。

最坏情况划分

当每次划分把问题分解为一个规模为n-1的问题和一个规模为0的问题时，快速排序将产生最坏的情况（以后给出这个结论的证明，目前可以想象的出）。由于划分操作的时间复杂度为Θ(n)；当对一个长度为0的数组进行递归操作时，会直接返回，时间为T(0) = Θ(1)。于是算法总运行时间的递归式为：

$$T(n) = T(n-1) + T(0) + θ(n) = T(n-1) + θ(n)$$

可以解得，T(n) = θ(n²)。

由此可见，在划分都是最大程度不平均的情况下，快速排序算法的运行时间并不比插入排序好，甚至在某些情况下（比如数组本身已按大小排好序），不如插入排序。

最好情况划分

当每次划分都是最平均的时候（即问题规模被划分为[n/2]和【n/2】-1时），快速排序性能很好，总运行时间的递归式为：

$$T(n) = 2T(n/2) + θ(n)$$

可以解得，T(n) = θ(nlg n)。

平均划分

快速排序算法的平均运行时间，更接近于最好情况划分时间而非最坏情况划分时间。理解这一点的关键就是理解划分的平均性是如何反映到描述运行时间的递归式上的。

我们举个例子，对于一个9:1的划分，乍一看，这种划分是很不平均的。此时的运行时间递归式为：

$$T(n) = T(9n/10) + T(n/10) + cn$$

我们可以用如下递归树来更加形象地描述运行时间：

递归会在深度为log10/9n = Θ(lg n )处终止，因此，快速排序的总代价为O(nlgn)。可见，在直观上看起来非常不平均的划分，其运行时间是接近最好情况划分的时间的。事实上，对于任何一种常数比例的划分，其运行时间总是O(nlgn)。

3. 快速排序的随机化版本

以上的讨论其实都做了一个前提的声明，输入数据的所有排列都是等概率的。但是事实上这个条件并不一定总是成立。正如以前介绍的，有时候我们再在算法中引入随机性，可以使得算法对所以的输入都有较好的期望性能。很多人都选择随机化版本的快速排序作为大数据输入情况下的排序算法。

我们可以使用对数组的所有元素进行随机化排序的方式引入随机性。但为了简便，我们这里采用一种叫做**随机抽样(random sampling)**的随机化技术。

与以上始终采用A[r]作为“基准”的方法不同的是，随机抽样是从子数组A[p~r]中随机的抽取一个元素，把它作为“基准”，并与A[r]交换。其他的过程与上面介绍的一致。

下面是随机化版本的算法描述：

下面给出随机化版本的 Java 实现代码：

public static void main(String[] args) {
    int[] array = { 9, 2, 4, 0, 4, 1, 3, 5 };
    randomizedQuickSort(array, 0, array.length - 1);
    printArray(array);
}

public static int randomPartition(int[] array, int start, int end) {
    int random = (int) (Math.random() * ((end - start) + 1)) + start;
    int temp = array[random];
    array[random] = array[end];
    array[end] = temp;
    return partition(array, start, end);
}

/**
 * 快速排序
 *
 * @param array
 *            待排序数组
 * @param start
 *            待排序子数组的起始索引
 * @param end
 *            待排序子数组的结束索引
 */
public static void randomizedQuickSort(int[] array, int start, int end) {
    if (start < end) {
        int position = randomPartition(array, start, end);
        randomizedQuickSort(array, start, position - 1);
        randomizedQuickSort(array, position + 1, end);
    }
}

5. 算法分析2

在 算法分析1 中我们给出了快速排序性能的直观分析，以及它速度比较快的原因。这一节我们要给出一个更加严谨的分析。

最坏情况分析

我们用T(n)来表示规模为n的数组采用快速排序法排序所需的时间。PARTION函数生成的两个子数组的总长度是n-1，我们设其中一个的长度为q（0 ≤ q ≤ n-1），那么另一个的长度为n-q-1，因此有递归式：

$$T(n)=\max_{0≤q≤n-1}(T(q)+T(n-q-1)+\Theta(n))$$

我们容易知道，上式中q在端点上取得最大值。由此我们得到：

$$T(n)≤cn^2-c(2n-1)+\Theta(n)≤cn^2$$

因此，

$$T(n) = θ(n²) + θ(n) = θ(n²)$$

这就是说，快速排序算法的最坏情况的运行时间是θ(n²)；

期望运行时间

现在我们要求，在平均情况下，快速排序的运行时间。因此我们先对问题进行分析。

从算法的描述中我们可以看出，快速排序的运行时间是由在PARTITION操作上花费的时间决定的。每一次PARTITION操作都会从数组中挑选出一个数作为“基准”，因此PARTITION操作的总次数不会超过数组元素的总个数n。而每一次PARTITION操作的时间包括O(1)加上一段循环的时间。而在该循环的每次迭代中，都会比较“基准”元素与其他元素。因此，如果我们可以统计出总的比较次数（注意这里所说的比较次数是整个快速排序过程中比较的次数），就能够知道该循环的运行时间，从而就能给出快速排序的运行时间。

为了便于分析，不失一般性，我们将数组A的各个元素重命名为Z₁，Z₂，…Z_n，其中Zi表示数组A中第i小的元素；此外我们还定义Z_ij表示一个包含元素Z_i到Z_j（包括Z_i和Z_j）的集合，即Z_ij=｛Z_i，Z_i+1，… Z_j｝。

我们引入一个指示器随机变量X_ij来表示Z_i与Z_j是否进行了比较，即：

$$X_{ij}= \begin{cases} 0&,X_i与X_j没比较\\ 1&,X_i与X_j相比较 \end{cases}$$

因为每一对元素至多被计较一次，因此我们可以很容易算出总比较次数为：

$$X=\sum_{i=1}^{n-1}\sum_{j=i+1}^{1}X_{ij}$$

对上式两边取期望得：

$$E(x)=E(\sum_{i=1}^{n-1}\sum_{j=i+1}^{1}X_{ij})=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}E(X_{ij})=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}P(z_i与z_j进行比较)$$

下面我们来分析如何求P(zi与zj进行比较)。

我们先从一个简单的例子入手。考虑对一个包含数字1~10的数组A进行快速排序的情况。假设我们第一次进行PARTITION操作时，选定的“基准”元素是7，那么数组A将被划分为｛1,2,3,4,5,6｝和｛8,9,10｝两个数组，我们可以发现，这两个数组中彼此任何两个元素是不会相互比较的。因此，我们有如下断言：如果一个满足zi < X < zj（假设各元素互异）的元素x被选为“基准”后，zi 和zj就不会被比较了；如果zi在Zij的其他元素之前被选为“基准”，那么zi会与Zij中的其他所有元素进行比较。于是，我们有：

进而得到：

$$\begin{align} E[X] =& \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\frac 2 {j - i + 1} \\ =& \sum_{i=1}^{n-1}\sum_{k=1}^{n-i}\frac 2 {k + 1} \\ <& \sum_{i=1}^{n-1}\sum_{k=1}^{n}\frac 2 k \\ =& \sum_{i=1}^{n-1}O(lgn) \\ =& O(n lgn) \end{align}$$

由此我们可以得出结论：使用 RANDOMIZED-PARTITION ，在输入元素互异的情况下，快速排序 的期望运行时间是 $O(nlgn)$。