【IT168技术文档】

  排序和搜索是我们编程时最常用到的两种算法了，C++程序员们幸运一些，因为在C++标准库中就有各种通用的排序函数；而Delphi程序员就只有TList.Sort和TStringList.Sort可用了，所以Delphi程序员通常都把排序函数加入到自己的常用函数单元中。

  作为“通用排序函数”，自然要在“基于比较”的排序算法中选择，而其中的“快速排序”以其效率优势常使它成为程序员的首选。但快速排序也有一个常常另人担心的问题……它在最差情况下的时间复杂度是O(N2)。因此，悲观的程序员们通常会改用“堆排序”（在《C++标准程序库》一书中作者就推荐使用partial_sort，因为sort可能是用“快速排序”实现的而partial_sort则通常是用“堆排序实现的”）。

  为了能“既吃到鱼又不丢了熊掌”，很多程序员都在想办法改良“快速排序”，在不影响它的优秀的平均性能的前提下使它在最差情况下也可以获得可以忍受的性能，其中最成功的应该算是“Intro Sort”，而我在这里谈的是另一种方法。

  我们知道，“快速排序”的主要思想就是递归地对序列进行划分，用一个枢值把序列分成“大序列”和“小序列”。如果这个划分每次都是平均地“一分为二”，这时它就获得了非常好的的性能；而如果每次都是“畸形划分”——把序列分成长度为1和N-1的两部分，它就退化成了递归实现的“冒泡排序”，性能可想而知。要想对它进行改良，就要针对这种情况进行处理。一种思路是对划分进行改良，让它不产生“畸形划分”；另一种思路是对划分结果进行检查，如果是畸形划分则进行特殊处理。我这里的方法是第二种。

  基本思路就是，对划分结果产生的两个子序列的长度进行检查，如果其中一个与另一个的长度比超过某一界限，则认为这是一个“畸形划分”，对较短的子序列继续使用“快速排序”，而把较长的子序列平分为两个子序列分别排序，然后再进行一次合并。两个有序序列的合并是可以实现为线性的时间复杂度的，因此可以在每次都是畸形划分时仍然获得O(N*LogN)的时间复杂度。

  基本算法描述如下：

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;