排序是計算機算法中非常重要的一項，而排序算法又有不少實現(xiàn)方法，那么哪些排序算法比較有效率，哪些算法在特定場合比較有效，下面將用C++實現(xiàn)各種算法，并且比較他們的效率，讓我們對各種排序有個更深入的了解。

minheap.h 用于堆排序：

1 //使用時注意將關鍵碼加入 2 #ifndef MINHEAP_H 3 #define MINHEAP_H 4 #include <assert.h> 5 #include <iostream> 6 using std::cout; 7 using std::cin; 8 using std::endl; 9 using std::cerr; 10 #include <stdlib.h> 11 //const int maxPQSize = 50; 12 template <class Type> class MinHeap { 13 public: 14 MinHeap ( int maxSize );//根據(jù)最大長度建堆 15 MinHeap ( Type arr[], int n );//根據(jù)數(shù)組arr[]建堆 16 ~MinHeap ( ) { delete [] heap; } 17 const MinHeap<Type> & operator = ( const MinHeap &R );//重載賦值運算符 18 int Insert ( const Type &x );//插入元素 19 int RemoveMin ( Type &x );//移除關鍵碼最小的元素，并賦給x 20 int IsEmpty ( ) const { return CurrentSize == 0; }//檢查堆是否為空 21 int IsFull ( ) const { return CurrentSize == MaxHeapSize; }//檢查對是否滿 22 void MakeEmpty ( ) { CurrentSize = 0; }//使堆空 23 private: 24 enum { DefaultSize = 50 };//默認堆的大小 25 Type *heap; 26 int CurrentSize; 27 int MaxHeapSize; 28 void FilterDown ( int i, int m );//自上向下調(diào)整堆 29 void FilterUp ( int i );//自下向上調(diào)整堆 30 }; 31 template <class Type> MinHeap <Type>::MinHeap ( int maxSize ) 32 { 33 //根據(jù)給定大小maxSize,建立堆對象 34 MaxHeapSize = (DefaultSize < maxSize ) ? maxSize : DefaultSize; //確定堆大小 35 heap = new Type [MaxHeapSize]; //創(chuàng)建堆空間 36 CurrentSize = 0; //初始化 37 } 38 template <class Type> MinHeap <Type>::MinHeap ( Type arr[], int n ) 39 { 40 //根據(jù)給定數(shù)組中的數(shù)據(jù)和大小,建立堆對象 41 MaxHeapSize = DefaultSize < n ? n : DefaultSize; 42 heap = new Type [MaxHeapSize]; 43 if(heap==NULL){cerr <<"fail" <<endl;exit(1);} 44 for(int i =0; i< n; i++) 45 heap[i] = arr[i]; //數(shù)組傳送 46 CurrentSize = n; //當前堆大小 47 int currentPos = (CurrentSize-2)/2; //最后非葉 48 while ( currentPos >= 0 ) { 49 //從下到上逐步擴大,形成堆 50 FilterDown ( currentPos, CurrentSize-1 ); 51 currentPos-- ; 52 //從currentPos開始,到0為止, 調(diào)整currentPos--; } 53 } 54 } 55 template <class Type> void MinHeap<Type>::FilterDown ( const int start, const int EndOfHeap ) 56 { 57 // 結點i的左、右子樹均為堆，調(diào)整結點i 58 int i = start, j = 2*i+1; // j 是 i 的左子女 59 Type temp = heap[i]; 60 while ( j <= EndOfHeap ) { 61 if ( j < EndOfHeap && heap[j] > heap[j+1] ) 62 j++;//兩子女中選小者 63 if ( temp<= heap[j] ) break; 64 else { heap[i] = heap[j]; i = j; j = 2*j+1; } 65 } 66 heap[i] = temp; 67 } 68 template <class Type> int MinHeap<Type>::Insert ( const Type &x ) 69 { 70 //在堆中插入新元素 x 71 if ( CurrentSize == MaxHeapSize ) //堆滿 72 { 73 cout << "堆已滿" << endl; return 0; 74 } 75 heap[CurrentSize] = x; //插在表尾 76 FilterUp (CurrentSize); //向上調(diào)整為堆 77 CurrentSize++; //堆元素增一 78 return 1; 79 } 80 template <class Type> void MinHeap<Type>::FilterUp ( int start ) 81 { 82 //從 start 開始,向上直到0,調(diào)整堆 83 int j = start, i = (j-1)/2; // i 是 j 的雙親 84 Type temp = heap[j]; 85 while ( j > 0 ) { 86 if ( (heap[i].root->data.key )<= (temp.root->data.key) ) break; 87 else { heap[j] = heap[i]; j = i; i = (i -1)/2; } 88 } 89 heap[j] = temp; 90 } 91 template <class Type> int MinHeap <Type>::RemoveMin ( Type &x ) 92 { 93 if ( !CurrentSize ) 94 { 95 cout << "堆已空 " << endl; 96 return 0; 97 } 98 x = heap[0]; //最小元素出隊列 99 heap[0] = heap[CurrentSize-1]; 100 CurrentSize--; //用最小元素填補 101 FilterDown ( 0, CurrentSize-1 ); 102 //從0號位置開始自頂向下調(diào)整為堆 103 return 1; 104 } 105 #endif

sort.cpp 主要的排序函數(shù)集包括冒泡排序、快速排序、插入排序、希爾排序、計數(shù)排序：

1 //n^2 2 //冒泡排序V[n]不參與排序 3 void BubbleSort (int V[], int n ) 4 { 5 bool exchange; //設置交換標志置 6 for ( int i = 0; i < n; i++ ){ 7 exchange=false; 8 for (int j=n-1; j>i; j--) { //反向檢測，檢查是否逆序 9 if (V[j-1] > V[j]) //發(fā)生逆序，交換相鄰元素 10 { 11 int temp=V[j-1]; 12 V[j-1]=V[j]; 13 V[j]=temp; 14 exchange=true;//交換標志置位 15 } 16 } 17 18 if (exchange == false) 19 return; //本趟無逆序，停止處理 20 } 21 } 22 //插入排序,L[begin],L[end]都參與排序 23 void InsertionSort ( int L[], const int begin, const int end) 24 { 25 //按關鍵碼 Key 非遞減順序對表進行排序 26 int temp; 27 int i, j; 28 for ( i = begin; i < end; i++ ) 29 { 30 if (L[i]>L[i+1]) 31 { 32 temp = L[i+1]; 33 j=i; 34 do 35 { 36 L[j+1]=L[j]; 37 if(j == 0) 38 { 39 j--; 40 break; 41 } 42 j--; 43 44 } while(temp<L[j]); 45 L[j+1]=temp; 46 } 47 } 48 } 49 //n*logn 50 //快速排序A[startingsub],A[endingsub]都參與排序 51 void QuickSort( int A[], int startingsub, int endingsub) 52 { 53 if ( startingsub >= endingsub ) 54 ; 55 else{ 56 int partition; 57 int q = startingsub; 58 int p = endingsub; 59 int hold; 60 61 do{ 62 for(partition = q ; p > q ; p--){ 63 if( A[q] > A[p]){ 64 hold = A[q]; 65 A[q] = A[p]; 66 A[p] = hold; 67 break; 68 } 69 } 70 for(partition = p; p > q; q++){ 71 if(A[p] < A[q]){ 72 hold = A[q]; 73 A[q] = A[p]; 74 A[p] = hold; 75 break; 76 } 77 } 78 79 }while( q < p ); 80 QuickSort( A, startingsub, partition - 1 ); 81 QuickSort( A, partition + 1, endingsub ); 82 } 83 } 84 //希爾排序,L[left],L[right]都參與排序 85 void Shellsort( int L[], const int left, const int right) 86 { 87 int i, j, gap=right-left+1; //增量的初始值 88 int temp; 89 do{ 90 gap=gap/3+1; //求下一增量值 91 for(i=left+gap; i<=right; i++) 92 //各子序列交替處理 93 if( L[i]<L[i-gap]){ //逆序 94 temp=L[i]; j=i-gap; 95 do{ 96 L[j+gap]=L[j]; //后移元素 97 j=j-gap; //再比較前一元素 98 }while(j>left&&temp<L[j]); 99 L[j+gap]=temp; //將vector[i]回送 100 } 101 }while(gap>1); 102 } 103 //n 104 //計數(shù)排序,L[n]不參與排序 105 void CountingSort( int L[], const int n ) 106 { 107 int i,j; 108 const int k =1001; 109 int tmp[k]; 110 int *R; 111 R = new int[n]; 112 for(i=0;i<k;i++) tmp[i]= 0; 113 for(j=0;j<n;j++) tmp[L[j]]++; 114 //執(zhí)行完上面的循環(huán)后，tmp[i]的值是L中等于i的元素的個數(shù) 115 for(i=1;i<k;i++) 116 tmp[i]=tmp[i]+tmp[i-1]; //執(zhí)行完上面的循環(huán)后， 117 //tmp[i]的值是L中小于等于i的元素的個數(shù) 118 for(j=n-1;j>=0;j--) //這里是逆向遍歷，保證了排序的穩(wěn)定性 119 { 120 121 R[tmp[L[j]]-1] = L[j]; 122 //L[j]存放在輸出數(shù)組R的第tmp[L[j]]個位置上 123 tmp[L[j]]--; 124 //tmp[L[j]]表示L中剩余的元素中小于等于L[j]的元素的個數(shù) 125 126 } 127 for(j=0;j<n;j++) L[j] = R[j]; 128 } 129 //基數(shù)排序 130 void printArray( const int Array[], const int arraySize ); 131 int getDigit(int num, int dig); 132 const int radix=10; //基數(shù) 133 void RadixSort(int L[], int left, int right, int d){ 134 //MSD排序算法的實現(xiàn)。從高位到低位對序列劃分，實現(xiàn)排序。d是第幾位數(shù)，d=1是最低位。left和right是待排序元素子序列的始端與尾端。 135 int i, j, count[radix], p1, p2; 136 int *auxArray; 137 int M = 5; 138 auxArray = new int[right-left+1]; 139 if (d<=0) return; //位數(shù)處理完遞歸結束 140 if (right-left+1<M){//對于小序列可調(diào)用直接插入排序 141 InsertionSort(L,left,right); return; 142 } 143 for (j=0; j<radix; j++) count[j]=0; 144 for (i=left; i<=right; i++) //統(tǒng)計各桶元素的存放位置 145 count[getDigit(L[i],d)]++; 146 for (j=1; j<radix; j++) //安排各桶元素的存放位置 147 count[j]=count[j]+count[j-1]; 148 for (i=right; i>=left; i--){ //將待排序序列中的元素按位置分配到各個桶中，存于助數(shù)組auxArray中 149 j=getDigit(L[i],d); //取元素L[i]第d位的值 150 auxArray[count[j]-1]=L[i]; //按預先計算位置存放 151 count[j]--; //計數(shù)器減1 152 } 153 for (i=left, j=0; i<=right; i++, j++) 154 L[i]=auxArray[j]; //從輔助數(shù)組順序寫入原數(shù)組 155 delete []auxArray; 156 for (j=0; j<radix; j++){ //按桶遞歸對d-1位處理 157 p1=count[j]+left; //取桶始端,相對位置，需要加上初值$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ 158 (j+1 <radix )?(p2=count[j+1]-1+left):(p2=right) ; //取桶尾端 159 // delete []count; 160 if(p1<p2){ 161 RadixSort(L, p1, p2, d-1); //對桶內(nèi)元素進行基數(shù)排序 162 // printArray(L,10); 163 } 164 } 165 166 } 167 int getDigit(int num, int dig) 168 { 169 int myradix = 1; 170 /* for(int i = 1;i<dig;i++) 171 { 172 myradix *= radix; 173 }*/ 174 switch(dig) 175 { 176 case 1: 177 myradix = 1; 178 break; 179 case 2: 180 myradix = 10; 181 break; 182 case 3: 183 myradix = 1000; 184 break; 185 case 4: 186 myradix = 10000; 187 break; 188 default: 189 myradix = 1; 190 break; 191 } 192 return (num/myradix)%radix; 193 }

maintest.cpp 測試例子：

1 #include<iostream> 2 using std::cout; 3 using std::cin; 4 using std::endl; 5 #include <cstdlib> 6 #include <ctime> 7 #include<iostream> 8 using std::cout; 9 using std::cin; 10 using std::ios; 11 using std::cerr; 12 using std::endl; 13 #include<iomanip> 14 using std::setw; 15 using std::fixed; 16 #include<fstream> 17 using std::ifstream; 18 using std::ofstream; 19 using std::flush; 20 #include<string> 21 using std::string; 22 #include <stdio.h> 23 #include <stdlib.h> 24 #include <time.h> 25 #include"minheap.h" 26 void BubbleSort(int arr[], int size);//冒泡排序 27 void QuickSort( int A[], int startingsub, int endingsub);//快速排序 28 void InsertionSort ( int L[], const int begin,const int n);//插入排序 29 void Shellsort( int L[], const int left, const int right);//希爾排序 30 void CountingSort( int L[], const int n );//計數(shù)排序 31 int getDigit(int num, int dig);//基數(shù)排序中獲取第dig位的數(shù)字 32 void RadixSort(int L[], int left, int right, int d);//基數(shù)排序 33 void printArray( const int Array[], const int arraySize );//輸出數(shù)組 34 int main() 35 { 36 clock_t start, finish; 37 double duration; 38 /* 測量一個事件持續(xù)的時間*/ 39 ofstream *ofs; 40 string fileName = "sortResult.txt"; 41 ofs = new ofstream(fileName.c_str(),ios::out|ios::app); 42 const int size = 100000; 43 int a[size]; 44 int b[size]; 45 srand(time(0)); 46 ofs->close(); 47 for(int i = 0; i < 20;i++) 48 { 49 ofs->open(fileName.c_str(),ios::out|ios::app); 50 if( ofs->fail()){ 51 cout<<"!!"; 52 ofs->close(); 53 } 54 for(int k =0; k <size;k++) 55 { 56 a[k] = rand()%1000; 57 b[k] = a[k]; 58 59 } 60 /* for( k =0; k <size;k++) 61 { 62 a[k] = k; 63 b[k] = a[k]; 64 65 } */ 66 //printArray(a,size); 67 //計數(shù)排序 68 for( k =0; k <size;k++) 69 { 70 a[k] = b[k]; 71 } 72 start = clock(); 73 CountingSort(a,size); 74 75 finish = clock(); 76 // printArray(a,size); 77 78 duration = (double)(finish - start) / CLOCKS_PER_SEC; 79 printf( "%s%f seconds\n", "計數(shù)排序:",duration ); 80 *ofs<<"第"<<i<<"次:\n " <<"排序內(nèi)容：0~999共" << size << " 個整數(shù)\n" ; 81 *ofs<<"第"<<i<<"次計數(shù)排序:\n " <<" Time: " <<fixed<< duration << " seconds\n"; 82 //基數(shù)排序 83 for( k =0; k <size;k++) 84 { 85 a[k] = b[k]; 86 } 87 start = clock(); 88 RadixSort(a, 0,size-1, 3); 89 finish = clock(); 90 // printArray(a,size); 91 92 duration = (double)(finish - start) / CLOCKS_PER_SEC; 93 printf( "%s%f seconds\n", "基數(shù)排序:",duration ); 94 *ofs<<"第"<<i<<"次基數(shù)排序:\n " <<" Time: " << duration << " seconds\n"; 95 //堆排序 96 MinHeap<int> mhp(a,size); 97 start = clock(); 98 for( k =0; k <size;k++) 99 { 100 mhp.RemoveMin(a[k]); 101 } 102 finish = clock(); 103 // printArray(a,size); 104 duration = (double)(finish - start) / CLOCKS_PER_SEC; 105 printf( "%s%f seconds\n", "堆排序:",duration ); 106 *ofs<<"第"<<i<<"次堆排序:\n " <<" Time: " << duration << " seconds\n"; 107 //快速排序 108 for( k =0; k <size;k++) 109 { 110 a[k] = b[k]; 111 112 } 113 //printArray(a,size); 114 start = clock(); 115 QuickSort(a,0,size-1); 116 finish = clock(); 117 // printArray(a,size); 118 duration = (double)(finish - start) / CLOCKS_PER_SEC; 119 printf( "%s%f seconds\n", "快速排序:",duration ); 120 *ofs<<"第"<<i<<"次快速排序:\n " <<" Time: " << duration << " seconds\n"; 121 //希爾排序 122 for( k =0; k <size;k++) 123 { 124 a[k] = b[k]; 125 } 126 start = clock(); 127 Shellsort(a,0,size-1); 128 129 finish = clock(); 130 // printArray(a,size); 131 132 duration = (double)(finish - start) / CLOCKS_PER_SEC; 133 printf( "%s%f seconds\n", "希爾排序:",duration ); 134 *ofs<<"第"<<i<<"次希爾排序:\n " <<" Time: " << duration << " seconds\n"; 135 136 //插入排序 137 for( k =0; k <size;k++) 138 { 139 a[k] = b[k]; 140 } 141 start = clock(); 142 InsertionSort (a,0,size-1); 143 finish = clock(); 144 // printArray(a,size); 145 146 duration = (double)(finish - start) / CLOCKS_PER_SEC; 147 printf( "%s%f seconds\n", "插入排序:",duration ); 148 *ofs<<"第"<<i<<"次插入排序:\n " <<" Time: " << duration << " seconds\n"; 149 //冒泡排序 150 for( k =0; k <size;k++) 151 { 152 a[k] = b[k]; 153 } 154 start = clock(); 155 BubbleSort(a,size); 156 finish = clock(); 157 // printArray(a,size); 158 159 duration = (double)(finish - start) / CLOCKS_PER_SEC; 160 printf( "%s%f seconds\n", "冒泡排序:",duration ); 161 *ofs<<"第"<<i<<"次冒泡排序:\n " <<" Time: " << duration << " seconds\n"; 162 ofs->close(); 163 } 164 return 0; 165 } 166 void printArray( const int Array[], const int arraySize ) 167 { 168 for( int i = 0; i < arraySize; i++ ) { 169 cout << Array[ i ] << " "; 170 if ( i % 20 == 19 ) 171 cout << endl; 172 } 173 cout << endl; 174 }

排序算法性能仿真：

排序內(nèi)容：從0~999中隨機產(chǎn)生，共100000 個整數(shù)，該表中單位為秒。

次數(shù)	計數(shù)排序	基數(shù)排序	堆排序	快速排序	希爾排序	直接插入排序	冒泡排序
1	0.0000	0.0310	0.0470	0.0470	0.0310	14.7970	58.0930
2	0.0000	0.0470	0.0310	0.0470	0.0470	16.2500	53.3280
3	0.0000	0.0310	0.0310	0.0310	0.0310	14.4850	62.4380
4	0.0000	0.0320	0.0320	0.0470	0.0310	17.1090	61.8440
5	0.0000	0.0310	0.0470	0.0470	0.0310	16.9380	62.3280
6	0.0000	0.0310	0.0310	0.0470	0.0310	16.9380	57.7030
7	0.0000	0.0310	0.0470	0.0310	0.0310	16.8750	61.9380
8	0.0150	0.0470	0.0310	0.0470	0.0320	17.3910	62.8600
9	0.0000	0.0320	0.0470	0.0460	0.0310	16.9530	62.2660
10	0.0000	0.0470	0.0310	0.0470	0.0310	17.0160	60.1410
11	0.0000	0.0930	0.0780	0.0320	0.0310	14.6090	54.6570
12	0.0000	0.0310	0.0320	0.0310	0.0310	15.0940	62.3430
13	0.0000	0.0310	0.0310	0.0470	0.0310	17.2340	61.9530
14	0.0000	0.0320	0.0470	0.0470	0.0310	16.9060	61.0620
15	0.0000	0.0320	0.0320	0.0460	0.0320	16.7810	62.5310
16	0.0000	0.0470	0.0470	0.0620	0.0310	17.2350	57.1720
17	0.0150	0.0160	0.0320	0.0470	0.0310	14.1400	52.0320
18	0.0150	0.0160	0.0310	0.0310	0.0310	14.1100	52.3590
19	0.0000	0.0310	0.0320	0.0460	0.0320	14.1090	51.8750
20	0.0000	0.0310	0.0320	0.0460	0.0320	14.0780	52.4840
21	0.0150	0.0780	0.0470	0.0470	0.0310	16.3750	59.5150
22	0.0000	0.0310	0.0310	0.0470	0.0320	16.8900	60.3440
23	0.0000	0.0310	0.0310	0.0310	0.0310	16.3440	60.0930
24	0.0000	0.0310	0.0310	0.0470	0.0310	16.3440	60.5780
25	0.0000	0.0320	0.0470	0.0470	0.0470	16.3590	59.7810
26	0.0160	0.0470	0.0310	0.0470	0.0310	16.1250	61.0620
27	0.0000	0.0310	0.0470	0.0470	0.0310	16.7810	59.6100
28	0.0150	0.0320	0.0320	0.0470	0.0310	16.9220	56.8130
29	0.0000	0.0310	0.0310	0.0310	0.0310	15.0790	57.8120
30	0.0000	0.0310	0.0320	0.0460	0.0320	14.7810	58.8280
31	0.0000	0.0310	0.0310	0.0470	0.0310	15.8590	59.1400
32	0.0000	0.0470	0.0320	0.0310	0.0310	16.0940	59.1560
33	0.0000	0.0470	0.0310	0.0310	0.0310	15.9850	59.1400
34	0.0000	0.0310	0.0310	0.0470	0.0320	16.0150	59.2500
35	0.0000	0.0310	0.0470	0.0470	0.0310	16.7660	57.9840
36	0.0000	0.0310	0.0320	0.0470	0.0310	15.3750	59.0470
37	0.0000	0.0320	0.0460	0.0470	0.0320	16.0310	58.9060
38	0.0000	0.0310	0.0310	0.0470	0.0310	15.9530	57.2650
39	0.0160	0.0310	0.0470	0.0470	0.0310	15.9530	57.5160
40	0.0150	0.0310	0.0320	0.0470	0.0310	14.7030	56.6710
平均值	0.0031	0.0360	0.0372	0.0437	0.0320	15.9946	58.7480
最小值	0.0000	0.0160	0.0310	0.0310	0.0310	14.0780	51.8750
最大值	0.0160	0.0930	0.0780	0.0620	0.0470	17.3910	62.8600

?

?from:http://www.nowamagic.net/librarys/veda/detail/294

轉載于:https://www.cnblogs.com/bizhu/archive/2012/08/12/2634340.html

總結

以上是生活随笔為你收集整理的各排序算法的C++实现与性能测试(转)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。