排序和搜索是我们编程时最常用到的两种算法了，C++程序员们幸运一些，因为在C++标准库中就有各种通用的排序函数；而Delphi程序员就只有TList.Sort和TStringList.Sort可用了，所以Delphi程序员通常都把排序函数加入到自己的常用函数单元中。
作为“通用排序函数”，自然要在“基于比较”的排序算法中选择，而其中的“快速排序”以其效率优势常使它成为程序员的首选。但快速排序也有一个常常另人担心的问题……它在最差情况下的时间复杂度是O(N2)。因此，悲观的程序员们通常会改用“堆排序”（在《C++标准程序库》一书中作者就推荐使用partial_sort，因为sort可能是用“快速排序”实现的而partial_sort则通常是用“堆排序实现的”）。
为了能“既吃到鱼又不丢了熊掌”，很多程序员都在想办法改良“快速排序”，在不影响它的优秀的平均性能的前提下使它在最差情况下也可以获得可以忍受的性能，其中最成功的应该算是“Intro Sort”，而我在这里谈的是另一种方法。
我们知道，“快速排序”的主要思想就是递归地对序列进行划分，用一个枢值把序列分成“大序列”和“小序列”。如果这个划分每次都是平均地“一分为二”，这时它就获得了最佳的性能；而如果每次都是“畸形划分”——把序列分成长度为1和N-1的两部分，它就退化成了递归实现的“冒泡排序”，性能可想而知。要想对它进行改良，就要针对这种情况进行处理。一种思路是对划分进行改良，让它不产生“畸形划分”；另一种思路是对划分结果进行检查，如果是畸形划分则进行特殊处理。我这里的方法是第二种。
基本思路就是，对划分结果产生的两个子序列的长度进行检查，如果其中一个与另一个的长度比超过某一界限，则认为这是一个“畸形划分”，对较短的子序列继续使用“快速排序”，而把较长的子序列平分为两个子序列分别排序，然后再进行一次合并。两个有序序列的合并是可以实现为线性的时间复杂度的，因此可以在每次都是畸形划分时仍然获得O(NLogN)的时间复杂度。
基本算法描述如下：
procedure Sort(Data, Size);
begin
M = Partition(Data, Size);
MoreData = @Data[M + 1];
MoreSize = Size - M - 1;
Size = M;
if Size M then
begin
Swap(MoreData, Data);
Swap(MoreSize, Size);
end;
Sort(Data, Size);
if MoreSize div MAX_RATIO Size then
begin
Sort(MoreData, MoreSize div 2);
Sort(@MoreData[MoreSize div 2], MoreSize - MoreSize div 2);
Merge(MoreData, MoreSize div 2, MoreSize);
end
else
Sort(MoreData, MoreSize);
end;
其中Partition就是众所周知的用于“快速排序”的划分子程序，Merge(Data, First,Size)把Data中[0,First)和[First, Size)两个有序列合并为一个有序序列并存放在Data中。上面的算法认为Partition划分的位置M处的值就是划分的枢值，也就是说序列可以分成[0,M-1]、[M,M]和[M+1,Size-1]三部分。如果Partition的实现不能保证这一点，则MoreData应为Data[M]，而MoreSize也应为Size - M。
现在简单分析一下这个排序，最好情况是在Partition每次划分都是平均划分时，这时合并不会发生，它等同于“快速排序”。而在最差情况下，每次Partition都会把序列分成长度为1和N-1的两部分，这时它就变成了递归实现的“二路归并排序”，但在每次合并前都进行了约N次比较，作用只是分出一个元素不参与合并。因此这个排序的时间复杂度仍然是O(N*LogN)，比较次数大约是归并排序的二倍。
关于MAX_RATIO的选择，根据我的经验，应该是选择4-16之间的数字比较好，我选择的是8。
我实际上实现时比上面说的要复杂一些，一是在序列长度不大于16时改用插入排序，二是去掉了一个递归。然后作了一些效率上的测试，数据是500,000个长度为10的字符串，大致如下：
随机分布，500000个元素：
Sort:时间：3.31；比较次数：10843175。
QuickSort:时间：3.28；比较次数：10936357。
IntroSort:时间：3.35；比较次数：10958355。
MergeSort:时间：4.20；比较次数：13502620。
正序分布，500000个元素：
Sort:时间：1.71；比较次数：8401712。
QuickSort:时间：1.91；比较次数：9262161。
IntroSort:时间：1.80；比较次数：8401712。
MergeSort:时间：1.72；比较次数：4766525。
逆序分布，500000个元素：
Sort:时间：2.38；比较次数：11737937。
QuickSort:时间：2.54；比较次数：12619014。
IntroSort:时间：2.38；比较次数：11293745。
MergeSort:时间：1.69；比较次数：4192495。
相同值，500000个元素：
Sort:时间：1.41；比较次数：8401712。
QuickSort:时间：1.47；比较次数：9262161。
IntroSort:时间：1.40；比较次数：8401712。
MergeSort:时间：1.43；比较次数：4766525。
波形分布（波长1000），500000个元素：
Sort:时间：2.52；比较次数：10658948。
QuickSort:时间：2.97；比较次数：12971845。
IntroSort:时间：3.02；比较次数：12672744。
MergeSort:时间：2.71；比较次数：7978745。
峰形分布（前半段为正序，后半段为前半段的逆转），500000个元素：
Sort:时间：2.42；比较次数：10401407。
IntroSort:时间：5.13；比较次数：19211813。
MergeSort:时间：1.88；比较次数：5176855。
谷形分布（峰形分布的逆转），500000个元素：
Sort:时间：2.29；比较次数：10944792。
IntroSort:时间：5.29；比较次数：17898801。
MergeSort:时间：1.90；比较次数：5282136。
由于这个排序的最差分布不是很好寻找，我修改了一下Partition函数，使正序分成成为它的不利分布，然后在同一台机器上测了一下：
正序分布，500000个元素：
Sort:时间：2.77；比较次数：12011738。
IntroSort:时间：4.31；比较次数：19212426。
MergeSort:时间：1.73；比较次数：4766525。
相同值，500000个元素：
Sort:时间：1.41；比较次数：8401712。
QuickSort:时间：1.47；比较次数：9262161。
IntroSort:时间：1.40；比较次数：8401712。
MergeSort:时间：1.43；比较次数：4766525。
波形分布（波长1000），500000个元素：
Sort:时间：2.52；比较次数：10658948。
QuickSort:时间：2.97；比较次数：12971845。
IntroSort:时间：3.02；比较次数：12672744。
MergeSort:时间：2.71；比较次数：7978745。
峰形分布（前半段为正序，后半段为前半段的逆转），500000个元素：
Sort:时间：2.42；比较次数：10401407。
IntroSort:时间：5.13；比较次数：19211813。
MergeSort:时间：1.88；比较次数：5176855。
谷形分布（峰形分布的逆转），500000个元素：
Sort:时间：2.29；比较次数：10944792。
IntroSort:时间：5.29；比较次数：17898801。
MergeSort:时间：1.90；比较次数：5282136。
由于这个排序的最差分布不是很好寻找，我修改了一下Partition函数，使正序分成成为它的不利分布，然后在同一台机器上测了一下：
正序分布，500000个元素：
Sort:时间：2.77；比较次数：12011738。
IntroSort:时间：4.31；比较次数：19212426。
MergeSort:时间：1.73；比较次数：4766525。
相同值，500000个元素：
Sort:时间：1.41；比较次数：8401712。
QuickSort:时间：1.47；比较次数：9262161。
IntroSort:时间：1.40；比较次数：8401712。
MergeSort:时间：1.43；比较次数：4766525。
波形分布（波长1000），500000个元素：
Sort:时间：2.52；比较次数：10658948。
QuickSort:时间：2.97；比较次数：12971845。
IntroSort:时间：3.02；比较次数：12672744。
MergeSort:时间：2.71；比较次数：7978745。
峰形分布（前半段为正序，后半段为前半段的逆转），500000个元素：
Sort:时间：2.42；比
阅读(178)
（责任编辑：城市网）