极光炫影

以下内容为极光炫影原创，转载请注明出处http://kennyblog.yculblog.com，谢谢！

一直以来，C++的sort函数都被其fans津津乐道。的确，看过STL源代码的人都知道sort函数其实是一个综合性的排序函数，其会根据待排序数据的规模自动调整算法，被其动态调用的算法包括partitional_sort、insertion_sort和heap_sort等，当然，不同版本的STL可能选择的算法不同。到底sort的效率如何？在何种场合下更加高效？为什么会高效？带着这些问题，我编写了本文所用的测试程序。

本文作为对比，我写了一个insertion_sort、一个heap_sort和一个类似P.J.STL的sort函数。其中sort函数采用了一个复杂的三数中值分割法来消除有序数列对快速排序的影响，这个算法来自P.J.STL，试验证明，这个算法对解决有序数列造成的影响非常奏效。

本文采用的测试平台是我的多核笔记本（T2300 + 1G DDR2 533MHz内存）和MS Windows XP SP2，编译器采用MS VS2005的VC8，用Release模式编译。测试用计时我采用了多核计算机在Windows平台下能得到的最高的时钟分辨率，所以测试所得时间一般认为比较可信。

我分别用随机、升序和降序三种数据进行了测试。结果如下：
// 随机数据 N = 100 InsertionSort Time Usage: 0.000011s HeapSort Time Usage : 0.000016s SuperSort Time Usage : 0.000013s STL sort Time Usage : 0.000022s CRT qsort Time Usage : 0.000010s N = 1000 InsertionSort Time Usage: 0.000623s HeapSort Time Usage : 0.000196s SuperSort Time Usage : 0.000160s STL sort Time Usage : 0.000225s CRT qsort Time Usage : 0.000073s N = 10000 HeapSort Time Usage : 0.002857s SuperSort Time Usage : 0.002171s STL sort Time Usage : 0.003009s CRT qsort Time Usage : 0.000879s N = 100000 HeapSort Time Usage : 0.040760s SuperSort Time Usage : 0.025473s STL sort Time Usage : 0.034072s CRT qsort Time Usage : 0.010616s N = 1000000 HeapSort Time Usage : 1.399524s SuperSort Time Usage : 0.462006s STL sort Time Usage : 0.514762s CRT qsort Time Usage : 0.125665s N = 10000000 HeapSort Time Usage : 24.607956s SuperSort Time Usage : 6.836967s STL sort Time Usage : 7.937051s CRT qsort Time Usage : 1.466362s // 升序数据 N = 100 InsertionSort Time Usage: 0.000003s HeapSort Time Usage : 0.000015s SuperSort Time Usage : 0.000005s STL sort Time Usage : 0.000008s CRT qsort Time Usage : 0.000010s N = 1000 InsertionSort Time Usage: 0.000008s HeapSort Time Usage : 0.000179s SuperSort Time Usage : 0.000036s STL sort Time Usage : 0.000063s CRT qsort Time Usage : 0.000073s N = 10000 HeapSort Time Usage : 0.002446s SuperSort Time Usage : 0.000644s STL sort Time Usage : 0.000829s CRT qsort Time Usage : 0.000884s N = 100000 HeapSort Time Usage : 0.030731s SuperSort Time Usage : 0.007948s STL sort Time Usage : 0.010571s CRT qsort Time Usage : 0.010588s N = 1000000 HeapSort Time Usage : 0.438595s SuperSort Time Usage : 0.098881s STL sort Time Usage : 0.127338s CRT qsort Time Usage : 0.125350s N = 10000000 HeapSort Time Usage : 5.400403s SuperSort Time Usage : 1.267556s STL sort Time Usage : 1.593427s CRT qsort Time Usage : 1.467023s // 降序数据 N = 100 InsertionSort Time Usage: 0.000015s HeapSort Time Usage : 0.000014s SuperSort Time Usage : 0.000005s STL sort Time Usage : 0.000011s CRT qsort Time Usage : 0.000010s N = 1000 InsertionSort Time Usage: 0.001230s HeapSort Time Usage : 0.000168s SuperSort Time Usage : 0.000063s STL sort Time Usage : 0.000098s CRT qsort Time Usage : 0.000073s N = 10000 HeapSort Time Usage : 0.002306s SuperSort Time Usage : 0.000851s STL sort Time Usage : 0.001148s CRT qsort Time Usage : 0.000957s N = 100000 HeapSort Time Usage : 0.029660s SuperSort Time Usage : 0.010131s STL sort Time Usage : 0.013687s CRT qsort Time Usage : 0.010517s N = 1000000 HeapSort Time Usage : 0.402304s SuperSort Time Usage : 0.120137s STL sort Time Usage : 0.162632s CRT qsort Time Usage : 0.125732s N = 10000000 HeapSort Time Usage : 5.193652s SuperSort Time Usage : 1.482605s STL sort Time Usage : 1.875436s CRT qsort Time Usage : 1.462693s

结果表明：

1、插入排序在数据量很小的情况下，特别是数据有序的情况下，有着惊人的成绩，表现超过了其他nlogn的排序，这于那些算法的复杂度有关
2、采用了三数中值分割法并进行一定小数组优化的快速排序完胜堆排序，数据越大这种优势越明显
3、qsort没有传说中的弱，有时候甚至很强，估计其四个参数中，那元素个数和元素大小两个参数非常重要，这有助于编译器优化；其采用的抗有序数列措施也很奏效，至少不必我的Sort里采用的差。
4、STL的sort不是每种情况下都能战胜qsort的，对基本类型，当其采用外部比较函数（即使该函数被声明为内联）的时候，效率大打折扣，但是内用内置的比较函数时，效率可以提高4倍以上，这得归功于编译器。

综合结论：

不要YY自己实现的排序函数的效率可以高过CRT和STL里相应的版本，那几乎不太可能，本文我写了很多代码来实现一个Sort，但结果除了在有序数据的测试中总体稍微比qsort快点外，在更加接近实际的随机数据测试中几乎是惨败——这个测试中，qsort几乎等于我把我的Sort函数中全部的比较函数换成<、==、>等运算符的速度了，可见编译器根据调用的参数在编译CRT的qsort时是多么智能！所以一般情况下还是推荐使用STL或者CRT的qsort。

附：我的测试程序
#include "stdio.h" #include "time.h" #include "stdlib.h" #include "windows.h" #include <algorithm> typedef long long I64; typedef int data_t; typedef data_t* data_p; typedef int (*data_compare)(data_t*, data_t*); inline int Compare(data_p p1, data_p p2) { return *p1 - *p2; } inline bool Compare2(const data_p& p1, const data_p& p2) { return *p1 < *p2; } inline int Compare3(const void* p1, const void* p2) { return *((data_p*)p1) - *((data_p*)p2); } // 交换 inline void SwapElement(data_p* _A, data_p* _B) { data_p _Temp; _Temp = *_A; *_A = *_B; *_B = _Temp; } // 插入排序 void InsertionSort(data_p* _First, data_p* _Last, data_compare pfnCompare) { data_p* _Curr; data_p* _Curr2; data_p _Temp; for(_Curr = _First + 1; _Curr < _Last; _Curr++) { _Temp = *_Curr; for(_Curr2 = _Curr; _First < _Curr2 && (*pfnCompare)(_Temp, *(_Curr2 - 1)) < 0; _Curr2--) *_Curr2 = *(_Curr2 - 1); *_Curr2 = _Temp; } } // 堆排序辅助函数 void HeapShiftDown(data_p* _First, data_p* _Last, data_p* _This, data_compare pfnCompare) { data_p _Temp = *_This; // 暂存堆顶元素 unsigned _Index = _This - _First; for(_Index <<= 1; _First + ++_Index < _Last; _Index <<= 1) { if(_First + _Index + 1 < _Last && (*pfnCompare)(*(_First + _Index), *(_First + _Index + 1)) < 0) _Index++; if((*pfnCompare)(_Temp, *(_First + _Index)) < 0) { *_This = *(_First + _Index); _This = _First + _Index; } else break; } *_This = _Temp; } // 堆排序 void HeapSort(data_p* _First, data_p* _Last, data_compare pfnCompare) { data_p* _Curr; // 先构建一个大顶堆 for(_Curr = _First + ((_Last - _First) >> 1); _Curr >= _First; _Curr--) HeapShiftDown(_First, _Last, _Curr, pfnCompare); // 排序 for(_Last--; _Last > _First; _Last--) { SwapElement(_First, _Last); HeapShiftDown(_First, _Last, _First, pfnCompare); } } // 三中值控制 inline void QSortMedian3(data_p* _First, data_p* _Middle, data_p* _Last, data_compare pfnCompare) { if((*pfnCompare)(*_Middle, *_First) < 0) SwapElement(_First, _Middle); if((*pfnCompare)(*_Last, *_First) < 0) SwapElement(_First, _Last); if((*pfnCompare)(*_Last, *_Middle) < 0) SwapElement(_Middle, _Last); } // 增强版本中值控制 inline void QSortAdvancedMedian(data_p* _First, data_p* _Middle, data_p* _Last, data_compare pfnCompare) { if(40 < _Last - _First) { QSortMedian3(_First, _Middle, _Last, pfnCompare); } else { unsigned nStepQuad = (_Last - _First) >> 2; unsigned nStepOcta = nStepQuad >> 1; QSortMedian3(_First, _First + nStepOcta, _First + nStepQuad, pfnCompare); QSortMedian3(_Middle - nStepOcta, _Middle, _Middle + nStepOcta, pfnCompare); QSortMedian3(_Last - nStepQuad, _Last - nStepOcta, _Last, pfnCompare); QSortMedian3(_First + nStepOcta, _Middle, _Last - nStepOcta, pfnCompare); } } // 分区 void QSortPartition(data_p* _First, data_p* _Last, data_p** _LeftBounds, data_p** _RightBounds, data_compare pfnCompare) { data_p *_Middle = _First + ((_Last - _First) >> 1); data_p *_First1, *_First2, *_Last1, *_Last2; int nCompareResult; QSortAdvancedMedian(_First, _Middle, _Last - 1, pfnCompare); // 以_Middle为中心向左右两边扩展一个区间[_First1, _Last1)，使这个区间内元素的值都等于*_Middle for(_First1 = _Middle; _First < _First1 && (*pfnCompare)(*(_First1 - 1), *_Middle) == 0; _First1--); for(_Last1 = _Middle + 1; _Last1 < _Last && (*pfnCompare)(*_Middle, *_Last1) == 0; _Last1++); _First2 = _Last1; _Last2 = _First1; while(true) { // 向右搜索，碰到相等的就让其合并到原先的区间，碰到比枢轴小的就跳出循环等待交换 for( ; _First2 < _Last; ++_First2) { nCompareResult = (*pfnCompare)(*_First1, *_First2); if(nCompareResult == 0) SwapElement(_Last1++, _First2); else if(nCompareResult > 0) break; } // 同理，向左搜索 for( ; _First < _Last2; --_Last2) { nCompareResult = (*pfnCompare)(*_First1, *(_Last2 - 1)); if(nCompareResult == 0) SwapElement(--_First1, _Last2 - 1); else if(nCompareResult < 0) break; } // 两边都搜到边界了 if(_First2 == _Last && _Last2 == _First) break; // 前面搜到头了 if(_First == _Last2) { if(_Last1 < _First2) SwapElement(_First1, _Last1); _Last1++; SwapElement(_First1++, _First2++); } // 后面的搜到尾了 else if(_Last == _First2) { if(--_Last2 < --_First1) SwapElement(_First1, _Last2); SwapElement(_First1, --_Last1); } else { SwapElement(_First2++, --_Last2); } } *_LeftBounds = _First1; *_RightBounds = _Last1; } // 以QuickSort为框架结合各种排序算法的综合高效排序算法 void SortAux(data_p* _First, data_p* _Last, unsigned nDepthLimit, data_compare pfnCompare) { data_p* _LeftBounds; data_p* _RightBounds; // 对大数组进行快速排序 for( ; 64 < _Last - _First && 0 < nDepthLimit; ) { nDepthLimit >>= 1; nDepthLimit += nDepthLimit >> 1; QSortPartition(_First, _Last, &_LeftBounds, &_RightBounds, pfnCompare); if(_LeftBounds - _First > _Last - _RightBounds) { SortAux(_First, _LeftBounds, nDepthLimit, pfnCompare); _First = _RightBounds; } else { SortAux(_RightBounds, _Last, nDepthLimit, pfnCompare); _Last = _LeftBounds; } } // 递归层数受限了，对中数组（超过某个限度的数组）进行堆排序 if(64 < _Last - _First) HeapSort(_First, _Last, pfnCompare); // 对小数组进行插入排序 else InsertionSort(_First, _Last, pfnCompare); } // Sort驱动函数 void Sort(data_p* _First, data_p* _Last, data_compare pfnCompare) { SortAux(_First, _Last, _Last - _First, pfnCompare); } int main() { data_t* data; data_t** items_back; data_t** items; int i, n; I64 nFrequency; I64 nStartTime; I64 nFinishTime; QueryPerformanceFrequency((PLARGE_INTEGER)&nFrequency); srand(GetTickCount()); printf("N = "); while(scanf("%d", &n) == 1 && n > 0) { data = (data_t*)malloc(sizeof(data_t) * n); items_back = (data_t**)malloc(sizeof(data_t*) * n); items = (data_t**)malloc(sizeof(data_t*) * n); for(i = 0; i < n; ++i) { data[i] = n - i; items_back[i] = &data[i]; } printf("Test case generated.\n\n"); if(n < 10000) { memcpy(items, items_back, sizeof(data_t*) * n); QueryPerformanceCounter((PLARGE_INTEGER)&nStartTime); InsertionSort(items, items + n, Compare); QueryPerformanceCounter((PLARGE_INTEGER)&nFinishTime); printf("InsertionSort Time Usage: %.6lfs\n", (nFinishTime - nStartTime) / (double)nFrequency); } memcpy(items, items_back, sizeof(data_t*) * n); QueryPerformanceCounter((PLARGE_INTEGER)&nStartTime); HeapSort(items, items + n, Compare); QueryPerformanceCounter((PLARGE_INTEGER)&nFinishTime); printf("HeapSort Time Usage\t: %.6lfs\n", (nFinishTime - nStartTime) / (double)nFrequency); memcpy(items, items_back, sizeof(data_t*) * n); QueryPerformanceCounter((PLARGE_INTEGER)&nStartTime); Sort(items, items + n, Compare); QueryPerformanceCounter((PLARGE_INTEGER)&nFinishTime); printf("SuperSort Time Usage\t: %.6lfs\n", (nFinishTime - nStartTime) / (double)nFrequency); memcpy(items, items_back, sizeof(data_t*) * n); QueryPerformanceCounter((PLARGE_INTEGER)&nStartTime); std::sort(items, items + n, Compare2); QueryPerformanceCounter((PLARGE_INTEGER)&nFinishTime); printf("STL sort Time Usage\t: %.6lfs\n", (nFinishTime - nStartTime) / (double)nFrequency); memcpy(items, items_back, sizeof(data_t*) * n); QueryPerformanceCounter((PLARGE_INTEGER)&nStartTime); qsort(items, n, sizeof(data_p), Compare3); QueryPerformanceCounter((PLARGE_INTEGER)&nFinishTime); printf("CRT qsort Time Usage\t: %.6lfs\n", (nFinishTime - nStartTime) / (double)nFrequency); free(data); free(items_back); free(items); printf("\n\nN = "); } return 0; }