本文共 5796 字，大约阅读时间需要 19 分钟。
之前一共实现了6种比较常见的排序算法，分别是：
，，，，，
效率：
衡量一个算法的效率包括空间和时间，有时候还要考虑稳定性。
前3种排序的方法效率较低，实现也比较简单，适合规模比较小的排序，个人认为适合排序总量在10000以下的随机数组。
后3种排序的方法效率较高，实现稍微复杂一点，但也还好，适合规模较大的排序。
时间方面，前3种排序的复杂度都是O(N^2)，后3种排序的复杂度都是O(N*LogN)，即呈指数级减少（因为基本思路都是递归的方式分治）。当然了，这是平均情况。
空间方面，即是否需要额外的空间，只有归并排序需要一个数组长度相同的空间来存储排序的结果，即O(N)。快速排序的需要O(log2N)。其余排序都不需要额外的空间。
稳定性方面，只有插入排序和归并排序是稳定的。稳定性保证的是数组中值相等的数据在排序时顺序不变，这在纯int型数组时没什么意义，但如果是复杂数据结构的排序，如果改变了顺序则可能影响数据结构中其他字段的排序。
疑问：谁能告诉我为什么快速排序的空间复杂度是O(log2N)？
特点：
每种排序都有自己的特点，要不然也不会留传了这么久。以下是个人看法：
冒泡排序：比较SB，只适合教学，效率低，但易实现。但能保证稳定。
选择排序：比冒泡排序好一点，好的地方是交换次数少了，但仍然很SB。而且不稳定。
插入排序：有点像打扑克牌时的排序，但插入时会让数组的移动变多，如果是链表则效率很高。且能保证稳定。
归并排序：典型地递归分治，缺点是需要额外的空间来存储结果。但能保证稳定。
快速排序：跟归并排序很像，但区别是归并排序切分的中点是数组索引，快速排序切分的中点是第一个数据的值。相同的是，都要碰运气。但不稳定。
堆排序：思路很特别，花了好几个班车上的时间片，另外用了扑克牌演示每一步的过程才弄明白流程。但不稳定。
运行时间比较：
这里就专门写个测试程序来测试一下这6种排序算法的运行时间倒底区别有多大。
随机生成100,000个数：
const int N = 200000;int O = 0;int* GenRandom(){ srand( (unsigned)time( NULL ) ); int* a = new int[N]; for (int i = 0; i < N; i++) { a[i] = rand()*rand() ; } return a;} 用下面的代码来计算时间： SYSTEMTIME StartTime = {0};FILETIME StartFileTime = {0};SYSTEMTIME EndTime= {0};FILETIME SEndFileTime= {0};int _tmain(int argc, _TCHAR* argv[]){ int* a = GenRandom(); GetLocalTime(&StartTime); printf("timeBefore %d:%d:%d \r\n", StartTime.wMinute, StartTime.wSecond, StartTime.wMilliseconds); BubbleSort(a); /*SelectionSort(a); InsertSort(a); MergeSort(a,0,N-1); QuickSort(a,0,N-1); HeapSort(a,0,N);*/ GetLocalTime(&EndTime); printf("timeAfter %d:%d:%d \r\n", EndTime.wMinute, EndTime.wSecond, EndTime.wMilliseconds); return 0;} 依次得到的结果如下： BubbleSort：1分37秒818，是的，你没看错。。
SelectionSort ：12秒338。
InsertSort：1分11秒23。
MergeSort：1秒598
QuickSort：0秒036
HeapSort：0秒081
说多了都是泪....这才是100，000个数，假设要是千万级的，差别就更大了，可能冒泡需要几个小时。。而快速和堆排序都表现的相当优秀。这也难怪快速排序叫做快速排序。
实现代码：
以防我的代码实现的有问题，影响了测试效果，特将代码列与此，如果有不足之处请各位指教和指正：
// Defines the entry point for the console application.//#include "stdafx.h"#include "windows.h"#include "time.h"const int N = 100000;int O = 0;int* GenRandom(){ srand( (unsigned)time( NULL ) ); int* a = new int[N]; for (int i = 0; i < N; i++) { a[i] = rand()*rand(); } return a;}void swap(int& a, int& b){ int temp = 0; temp = a; a = b; b = temp;}//small -> largevoid SelectionSort(int* ua){ //round times，遍历N次 for (int i = 0; i < N-1; i++) { int nMinIndex = i; //最小值的索引 //每次确定一个值，从第一个值开始。。。第二次从第二个值开始 for (int j = i + 1; j < N; j++) { if( ua[nMinIndex] >= ua[j] ) { nMinIndex = j; } O++; } swap(ua[i], ua[nMinIndex] ); }}//small -> largevoid InsertSort(int* ua){ //round times for (int i = 1; i <= N; i++) { for (int j = i; j > 0; j--) { if( ua[j] < ua[j-1] ) { swap(ua[j], ua[j-1] ); } } } }//small -> largevoid BubbleSort(int* ua) { O = 0; //round times for (int i = 0; i < N; i++) { /*printf("round %d \r\n", i); for (int i = 0; i < N; i++) { printf("a[%d]=%d \r\n",i, *(ua+i)); } */ for (int j = 0; j < (N-i-1); j++) { if(ua[j] > ua[j+1]) { swap(ua[j], ua[j+1] ); } O++; } } } void Merge(int* ua, int nStart, int nMid, int nEnd){ int a[N]; int i = nStart; int j = nMid + 1; for (int k = nStart; k <= nEnd; k++) { a[k] = ua[k]; } for (int k = nStart; k <= nEnd; k++) { if(i > nMid) { ua[k] = a[j++]; } else if(j > nEnd) { ua[k] = a[i++]; } else if( a[j] < a[i]) { ua[k] = a[j++]; } else { ua[k] = a[i++]; } /*printf("round %d \r\n", k); for (int k = nStart; k < nEnd; k++) { printf("a[%d]=%d \r\n", k, *(ua + k)); } */ }}//small -> largevoid MergeSort(int* ua, int nStart, int nEnd){ //递归退出条件 if(nStart >= nEnd) { return; } int nMid = nStart + (nEnd - nStart) / 2; MergeSort(ua, nStart, nMid); MergeSort(ua, nMid+1, nEnd); Merge(ua, nStart, nMid, nEnd);}int QuickPartition(int* ua, int nStart, int nEnd){ int i = nStart; int j = nEnd + 1; //中点值 int nFlagValue = ua[nStart]; while(1) { //找到左边大于中点的值，记录索引 while( ua[++i] < nFlagValue ) { if( i == nEnd) { break; } } //找到右边小于中点的值，记录索引 while( ua[--j] > nFlagValue ) { if( j == nStart) { break; } } //两边向中间靠拢的过程中相遇则退出 if( i >= j) { break; } //交换两边的值 swap( ua[i], ua[j] ); } //将右边最后一个小于中点值的数与中点值交换位置， //保证中点值的左边都小于中点值，右边都大于中点值 swap( ua[nStart], ua[j] ); //返回将右边最后一个小于中点值的数的索引，做为右边部分的中点值。 return j;}void QuickSort(int* ua, int nStart, int nEnd){ //递归退出条件 if(nStart >= nEnd) { return; } int nMid = QuickPartition(ua, nStart, nEnd); QuickSort(ua, nStart, nMid-1); QuickSort(ua, nMid+1, nEnd);}void HeapAdjust(int* ua, int nStart, int nEnd){ int nMaxIndex = 0; while ( ( 2*nStart + 1) < nEnd ) { nMaxIndex = 2*nStart + 1; if ( ( 2*nStart + 2) < nEnd) { //比较左子树和右子树,记录较大值的Index if (ua[2*nStart + 1] < ua[2*nStart + 2]) { nMaxIndex++; } } //如果父结点大于子节点，则退出，否则交换 if (ua[nStart] > ua[nMaxIndex]) { break; } else { swap( ua[nStart], ua[nMaxIndex] ); //堆被破坏,继续递归调整 nStart = nMaxIndex; } } /*for (int i = 0; i < N; i++) { printf("%d ",ua[i]); } printf("\r\n");*/ //printf("%d ", O++);}void HeapSort(int* ua, int nStart, int nEnd){ for (int i = nEnd/2 -1; i >= 0 ; i--) { HeapAdjust( ua, i, nEnd); } for (int i = nEnd-1; i > 0; i--) { swap(ua[0], ua[i]); HeapAdjust(ua, 0, i); }}SYSTEMTIME StartTime = {0};FILETIME StartFileTime = {0};SYSTEMTIME EndTime= {0};FILETIME SEndFileTime= {0};int _tmain(int argc, _TCHAR* argv[]){ int* a = GenRandom(); GetLocalTime(&StartTime); printf("timeBefore %d:%d:%d \r\n", StartTime.wMinute, StartTime.wSecond, StartTime.wMilliseconds); //BubbleSort(a); //SelectionSort(a); //InsertSort(a); //MergeSort(a,0,N-1); //QuickSort(a,0,N-1); HeapSort(a,0,N); GetLocalTime(&EndTime); printf("timeAfter %d:%d:%d \r\n", EndTime.wMinute, EndTime.wSecond, EndTime.wMilliseconds); printf("times %d \r\n", O); return 0;} 转载地址：http://vmlgb.baihongyu.com/