数据结构与算法之ACM Fellow-算法 快速排序

数据结构与算法之ACM Fellow-算法 快速排序

本节的主题是 快速排序，它可能是应用最广泛的排序算法了。快速排序流行的原因是它实现简单、适用于各种不同的输入数据且在一般应用中比其他排序算法都要快得多。快速排序引人注目的特点包括它是原地排序（只需要一个很小的辅助栈），且将长度为

的数组排序所需的时间和

成正比。我们已经学习过的排序算法都无法将这两个优点结合起来。另外，快速排序的内循环比大多数排序算法都要短小，这意味着它无论是在理论上还是在实际中都要更快。它的主要缺点是非常脆弱，在实现时要非常小心才能避免低劣的性能。已经有无数例子显示许多种错误都能致使它在实际中的性能只有*方级别。幸好我们将会看到，由这些错误中学到的教训也大大改进了快速排序算法，使它的应用更加广泛。
2.3.1　基本算法

快速排序是一种分治的排序算法。它将一个数组 分成 两个子数组，将两部分独立地排序。快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。在第一种情况中，递归调用发生在处理整个数组 之前；在第二种情况中，递归调用发生在处理整个数组 之后。在归并排序中，一个数组被等分为两半；在快速排序中，切分（partition）的位置取决于数组的内容。快速排序的大致过程如图 2.3.1 所示。
图 2.3.1　快速排序示意图
快速排序的实现过程如算法 2.5 所示。
<blockquote>算法 2.5　快速排序
[code]public class Quick{public static void sort(Comparable[] a){   StdRandom.shuffle(a);          // 消除对输入的依赖   sort(a, 0, a.length - 1);}private static void sort(Comparable[] a, int lo, int hi){   if (hi = j) break;   exch(a, i, j);}exch(a, lo, j);       // 将v = a[j]放入正确的位置return j;             // a[lo..j-1]