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

这两个元素不需要参与划分。

compare_exchange()是比较-交换的一个封装： [cpp] view plaincopy?template <typename Item> void compare_exchange(Item &a, Item &b) { if (a > b) exchange(a, b); }

经过划分的优化后，除非碰上了Douglas McIlroy的无敌的对手(killer adversary)，否则基本上不必担心这个快速排序会退化成O(N2)，对于有序数据，这是一个很大的加速。目前，它还有一个明显的bug（导致它还不能运行）和其它可以优化的地方，不过接下来的优化会消除这个bug。

这个bug就是快速排序使用了三值取中法，这导致算法需要数组有3个元素才可以进行排序。现在先不考虑三值取中法，那么它应该实现成这样：

[cpp] view plaincopy?template <typename Item> void quick_sort(Item a[], int left, int right) { if (right <= left) return; int i = partition(a, left, right); quick_sort(a, left, i-1); quick_sort(a, i+1, right); }

我们来考察一下它还有什么瓶颈。

在快速排序算法的递归实现中，存在一种不太好的现象：随着递归层层深入，大量数据被分割成了小数组；快排对于大数组的划分可以迅速地将元素移动到它正确位置的附近，比如说对1024进行一次均等划分，那么某个元素可能会移动数百个单位位置，若进行4次均等划分，元素在正确位置上的概率就从1/1024骤升到1/64，考虑到64与1024的绝对数值，这是相当高的效率；然而对于小数组，快速排序的效率就不那么理想了，对于16个元素的数组，快速排序也要划分4次才能把它移动到正确的位置上，相对于之前几百个位置的移动，小数组排序一次只能移动几个单位的位置。 换句话说，快速排序对少量数据的划分远不如它对大量数据的划分这么划算，当排序进入到小数组阶段后，它将多次因为这些小数组而频繁调用自身，但获得的收益并不大。我姑且把这种现象叫做 小数组的边际效益

对大量数据排序时，我们应该在前期利用快速排序的特点，让这些数据迅速移动到正确位置附近，然后在后期消除小数组的边际效应。

消除边际效应的一个方法就是设定一个M值，当数组元素个数小于M时，视为小数组，此时快速排序就直接返回，最后把数组处理得差不多时，再用其它排序方法对数组进行最终

排序。那么M值应该取多少？又应该选择何种排序算法进行最终排序？

首先回答第二个问题，因为它的答案是显而易见的。对接近有序的数据排序，没有什么算法比插入排序(insertion sort)更合适了，插入排序的执行开销与所有元素偏离自己正确位置的距离成正比，实现如下：

[cpp] view plaincopy?template <typename Item> void insertion_sort(Item a[], int left, int right) { int min, i; for (i = left, min = 0; i <= right; ++i) if (a[min] > a[i]) min = i; exchange(a[min], a[left]); if (right-left < 2) return; for (i = left+2; i <= right; ++i) { Item t = a[i]; int j = i; while (a[j-1] > t) a[j] = a[--j]; a[j] = t; } }

排序一开始把最小值作交换到最左边的位置为哨兵(sentinel)，这样可以减少内循环中的代码。

现在回答第一个问题。可以想到，M值不能取太小，否则不能消除边际效应；但又不能取太大，否则会加重插入排序的负担。经过研究，M取5~25之间的值是最理想的，具体数值视实际情况而定。C++ STL的sort函数使用了同样的优化，在SGI版本的STL中，M=16。

现在可以消除由三值取中法遗留下来的bug了：

[cpp] view plaincopy?const int M = 16; 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_sort(a, left, i-1); quick_sort(a, i+1, right); } template <typename Item> void sort(Item a[], int left, int right)

{ quick_sort(a, left, right); insertion_sort(a, left, right); }

这个排序算法混合了快速排序和插入排序，也结合了它们各自的优点。

到目前为止，我们的快速排序对有序数据和随机数据都工作的很好，但是，如果数组中含有大量重复元素，比如将某个学校的学生按出生年份排序，那么上面的快速排序仍然不够快。再考虑一种极端情况：所有元素都相等，这时候应该不