怎样让快速排序(quick sort)更快？

怎样让快速排序（quick sort）更快？

快速排序(quick sort)是目前应用最广泛的排序算法，它的平均复杂度为O(NlogN)，但因其内循环较小，所以速度很快，而且不需要太多额外的空间（主要是递归调用所需的栈空间，对于随机文件不大于logN）。关于算法的基础介绍，网上已有很多讲解得很好的资料，如July同学的《快速排序算法》，我就不拾人牙慧了，切入正题。

快速排序有点像二分搜索(binary search)：思想很简单，算法很高效，大家都知道，实现很困难。快速排序的一大特点就是效率不稳定，运行时间与输入数据密切相关，原因在于，快排是基于划分(partition)的排序算法，划分操作决定了整个算法的效率。许多简单实现中，划分的基准(pivot)都取输入序列中的第一个或最后一个元素。对于随机数据而言，这是足够有效的；但对于已经有序或者逆序的数据，这种划分将导致快速排序的时间效率退化成O(N2)，空间使用也会达到O(N)。可见一个好的划分过程对快速排序多么重要，因此第一个加速就从划分开始。

划分(partition)

划分操作中有两个值得关注的方面：

划分的过程

划分的基准

快排中移动元素的实际操作由划分完成，因此划分过程必须快速。目前已知的一个非常高效的算法，通过从数组两端向中间扫描的方法来完全划分。

令划分的基准v放在数组最右边，指针i从left开始向右扫描，遇到大于v的值则停住；同时令指针j从right-1开始向左扫描，遇到小于v的值时停下来，交换i和j指向的值，然后重复上述过程，直至i与j相遇。

该算法维护了一个不变式：i左边的元素都小于v；j右边的元素都大于v。这个策略是线性时间地原地划分，只扫描数组一次就能完成，C++实现如下（请仔细斟酌）：

[cpp] view plaincopy?template <typename Item> int partition(Item a[], int left, int right) { int i = left-1, j = right; Item v = a[right]; for (;;) { while (a[++i] < v) {} while (a[--j] > v) if (j == left) break; if (i >= j) break; exchange(a[i], a[j]); }

exchange(a[i], a[right]); return i; }

其中exchange是简单的交换操作：

[cpp] view plaincopy?template <typename Item> void exchange(Item &a, Item &b) { Item temp = a; a = b; b = temp; }

说完了划分过程，再来说说更重要的基准选取。从根本上说，快速排序的效率依赖于分割文件的位置的选取。最理想的划分值能把数组分成相当的两部分，对于随机的输入数据，固定的选取数组最右端元素和其他选取方法是一样的，在平均情况下二者都会接近中间的位置。但是为了防止输入数据本身有序而引起快速排序退化的情况，必须采取一些手段。一旦成功地消除了这种异常，就是对快速排序一个很大的加速。 一种较为稳妥的方法是随机选取数组中的某个位置，而不是总是顽固地选择最右端的元素，这样确实可以避免排序的退化。

再回想我们为什么要取随机值？就是为了避免输入数据有序造成的异常，如果一种方法能够在这种情况下利用这种原有的有序性岂不是更好吗？三值取中法(median-of-three method)就是这样的方法，它的选取方法是先从数组的开头、结尾和中间选取3个元素，再取这3个元素的中间值作为划

分的基准。

首先，三值取中法本身带有一定的随机性，所以能够很好的处理随机数据；其次，它使得最坏情况几乎不可能发生，如果数组原本就具有有序性，那么按照原始的划分方法，取到的3个元素中必然有2个将被划分到大于（或小于）v的值所在的数组中，而三值取中法则扭转了这种不利；最后，与随机化方法相比，三值取中法省去了生成随机数的开销。 在实际实现中，可通过三交换法来实现三值取中法：

[cpp] view plaincopy?template <typename Item> void quick_sort(Item a[], int left, int right) { if (right-left < M) return; exchange(a[(left+right)/2], a[right-1]); compare_exchange(a[left], a[right-1]); compare_exchange(a[left], a[right]);

compare_exchange(a[right-1], a[right]); int i = partition(a, left+1, right-1); quick_sort2(a, left, i-1); quick_sort2(a, i+1, right); }

在排序之前，先将位于中间的元素交换到right-1的位置，然后分别对left、right-1、 right三个位置的元素进行三交换排序，这样a[right-1]就是中值，也是即将要用来划分的基准。经过三交换后，a[left]≤a[right-1]，a[right]≥a[right-1]，因此