各种排序算法的C++实现与性能比较

排序是计算机算法中非常重要的一项，而排序算法又有不少实现方法，那么哪些排序算法比较有效率，哪些算法在特定场合比较有效，下面将用C++实现各种算法，并且比较他们的效率，让我们对各种排序有个更深入的了解。

minheap.h 用于堆排序：

view sourceprint?001 //使用时注意将关键码加入 

002 #ifndef MINHEAP_H 

003 #define MINHEAP_H 

004 #include <assert.h> 

005 #include <iostream> 

006 using std::cout; 

007 using std::cin; 

008 using std::endl; 

009 using std::cerr; 

010 #include <stdlib.h> 

011 //const int maxPQSize = 50;   

012 template <class Type> class MinHeap { 

013 public:  

014     MinHeap ( int maxSize );//根据最大长度建堆 

015     MinHeap ( Type arr[], int n );//根据数组arr[]建堆 

016     ~MinHeap ( ) { delete [] heap; } 

017     const MinHeap<Type> & operator = ( const MinHeap &R );//重载赋值运算符 

018     int Insert ( const Type &x );//插入元素 

019     int RemoveMin ( Type &x );//移除关键码最小的元素，并赋给x 

020     int IsEmpty ( ) const { return CurrentSize == 0; }//检查堆是否为空      

021     int IsFull ( ) const { return CurrentSize == MaxHeapSize; }//检查对是否满 

022     void MakeEmpty ( ) { CurrentSize = 0; }//使堆空 

023 private:  

024     enum { DefaultSize = 50 };//默认堆的大小 

025     Type *heap;                  

026     int CurrentSize; 

027     int MaxHeapSize; 

028     void FilterDown ( int i, int m );//自上向下调整堆 

029     void FilterUp ( int i );//自下向上调整堆 

030 }; 

031   

032 template <class Type> MinHeap <Type>::MinHeap ( int maxSize ) 

033 { 

034     //根据给定大小maxSize,建立堆对象 

035     MaxHeapSize = (DefaultSize < maxSize ) ? maxSize : DefaultSize;          //确定堆大小 

036     heap = new Type [MaxHeapSize];  //创建堆空间 

037     CurrentSize = 0;                               //初始化 

038 } 

039   

040 template <class Type> MinHeap <Type>::MinHeap ( Type arr[], int n ) 

041 { 

042     //根据给定数组中的数据和大小,建立堆对象     

043     MaxHeapSize = DefaultSize < n ? n : DefaultSize; 

044     heap = new Type [MaxHeapSize];  

045     if(heap==NULL){cerr <<"fail" <<endl;exit(1);} 

046     for(int i =0; i< n; i++) 

047         heap[i] = arr[i];               //数组传送 

048     CurrentSize = n;       //当前堆大小 

049     int currentPos = (CurrentSize-2)/2;   //最后非叶 

050     while ( currentPos >= 0 ) {        

051         //从下到上逐步扩大,形成堆 

052         FilterDown ( currentPos, CurrentSize-1 ); 

053         currentPos-- ; 

054         //从currentPos开始,到0为止, 调整currentPos--; } 

055     } 

056 } 

057   

058 template <class Type> void MinHeap<Type>::FilterDown ( const int start, const int EndOfHeap ) 

059 { 

060     // 结点i的左、右子树均为堆，调整结点i 

061     int i = start,   j = 2*i+1;           // j 是 i 的左子女 

062     Type temp = heap[i]; 

063     while ( j <= EndOfHeap ) { 

064         if ( j < EndOfHeap && heap[j] > heap[j+1] ) 

065             j++;//两子女中选小者 

066         if ( temp<= heap[j] ) break; 

067         else { heap[i] = heap[j];  i = j;   j = 2*j+1; } 

068     } 

069     heap[i] = temp; 

070 } 

071   

072 template <class Type> int MinHeap<Type>::Insert ( const Type &x )  

073 { 

074     //在堆中插入新元素 x 

075     if ( CurrentSize == MaxHeapSize )       //堆满 

076     {  

077         cout << "堆已满" << endl;  return 0;  

078     } 

079     heap[CurrentSize] = x;           //插在表尾   

080     FilterUp (CurrentSize);          //向上调整为堆 

081     CurrentSize++;                       //堆元素增一 

082     return 1; 

083 } 

084   

085 template <class Type> void MinHeap<Type>::FilterUp ( int start )  

086 { 

087     //从 start 开始,向上直到0,调整堆 

088     int j = start,  i = (j-1)/2;    // i 是 j 的双亲 

089     Type temp = heap[j]; 

090     while ( j > 0 ) {       

091         if ( (heap[i].root->data.key )<= (temp.root->data.key) ) break; 

092         else {  heap[j] = heap[i];  j = i;  i = (i -1)/2; } 

093     } 

094     heap[j] = temp; 

095 } 

096 template <class Type> int MinHeap <Type>::RemoveMin ( Type &x )  

097 { 

098     if ( !CurrentSize ) 

099     {  

100         cout << "堆已空 " << endl;  

101         return 0;  

102     } 

103     x = heap[0];             //最小元素出队列 

104     heap[0] = heap[CurrentSize-1];     

105     CurrentSize--;        //用最小元素填补 

106     FilterDown ( 0, CurrentSize-1 ); 

107     //从0号位置开始自顶向下调整为堆 

108     return 1; 

109 }    

110 #endif

sort.cpp 主要的排序函数集包括冒泡排序、快速排序、插入排序、希尔排序、计数排序：

view sourceprint?001 //n^2 

002 //冒泡排序V[n]不参与排序 

003 void BubbleSort (int V[], int n )  

004 { 

005     bool exchange;       //设置交换标志置 

006     for ( int i = 0;  i < n;  i++ ){ 

007         exchange=false; 

008         for (int j=n-1; j>i; j--) { //反向检测，检查是否逆序 

009             if  (V[j-1] > V[j]) //发生逆序，交换相邻元素 

010             {  

011                 int temp=V[j-1];  

012                 V[j-1]=V[j]; 

013                 V[j]=temp;  

014                 exchange=true;//交换标志置位 

015             } 

016         } 

017           

018         if  (exchange == false) 

019             return; //本趟无逆序，停止处理 

020     } 

021 } 

022   

023   

024   

025 //插入排序,L[begin],L[end]都参与排序 

026 void InsertionSort ( int L[], const int begin, const int end) 

027 { 

028     //按关键码 Key 非递减顺序对表进行排序 

029     int temp; 

030     int i, j; 

031     for ( i = begin; i < end; i++ )  

032     { 

033         if  (L[i]>L[i+1])  

034         { 

035             temp = L[i+1];  

036             j=i; 

037             do 

038             { 

039                 L[j+1]=L[j]; 

040                 if(j == 0) 

041                 { 

042                     j--; 

043                     break; 

044                 } 

045                 j--; 

046                   

047             } while(temp<L[j]); 

048             L[j+1]=temp; 

049         } 

050     } 

051 } 

052 //n*logn 

053 //快速排序A[startingsub],A[endingsub]都参与排序 

054 void QuickSort( int A[], int startingsub, int endingsub) 

055 { 

056     if ( startingsub >= endingsub  ) 

057         ; 

058     else{ 

059         int partition; 

060         int q = startingsub; 

061         int p = endingsub; 

062         int hold; 

063           

064         do{ 

065             for(partition = q ; p > q ; p--){ 

066                 if( A[q] > A[p]){ 

067                     hold = A[q]; 

068                     A[q] = A[p]; 

069                     A[p] = hold; 

070                     break; 

071                 } 

072             } 

073             for(partition = p; p > q; q++){ 

074                 if(A[p] < A[q]){ 

075                     hold = A[q]; 

076                     A[q] = A[p]; 

077                     A[p] = hold; 

078                     break; 

079                 } 

080             } 

081               

082         }while( q < p ); 

083         QuickSort( A, startingsub, partition - 1 ); 

084         QuickSort( A, partition + 1, endingsub ); 

085     } 

086 } 

087   

088 //希尔排序,L[left],L[right]都参与排序 

089 void Shellsort( int L[], const int left, const int right) 

090 { 

091     int i, j, gap=right-left+1;   //增量的初始值 

092     int temp; 

093     do{ 

094         gap=gap/3+1;               //求下一增量值 

095         for(i=left+gap; i<=right; i++) 

096             //各子序列交替处理 

097             if( L[i]<L[i-gap]){        //逆序 

098                 temp=L[i]; j=i-gap;      

099                 do{ 

100                     L[j+gap]=L[j];    //后移元素 

101                     j=j-gap;      //再比较前一元素 

102                 }while(j>left&&temp<L[j]); 

103                 L[j+gap]=temp;   //将vector[i]回送 

104             } 

105     }while(gap>1); 

106 }  

107   

108 //n 

109 //计数排序,L[n]不参与排序 

110 void CountingSort( int L[], const int n ) 

111 { 

112     int i,j; 

113     const int k =1001; 

114     int tmp[k]; 

115     int *R; 

116     R = new int[n]; 

117     for(i=0;i<k;i++) tmp[i]= 0;  

118     for(j=0;j<n;j++) tmp[L[j]]++;  

119     //执行完上面的循环后，tmp[i]的值是L中等于i的元素的个数 

120     for(i=1;i<k;i++) 

121         tmp[i]=tmp[i]+tmp[i-1]; //执行完上面的循环后， 

122     //tmp[i]的值是L中小于等于i的元素的个数 

123     for(j=n-1;j>=0;j--) //这里是逆向遍历，保证了排序的稳定性 

124     { 

125           

126         R[tmp[L[j]]-1] = L[j];   

127         //L[j]存放在输出数组R的第tmp[L[j]]个位置上 

128         tmp[L[j]]--;  

129         //tmp[L[j]]表示L中剩余的元素中小于等于L[j]的元素的个数  

130           

131     } 

132     for(j=0;j<n;j++) L[j] = R[j]; 

133 } 

134   

135 //基数排序 

136 void printArray( const int Array[], const int arraySize ); 

137 int getDigit(int num, int dig); 

138 const int radix=10;   //基数 

139 void RadixSort(int L[], int left, int right, int d){ 

140 //MSD排序算法的实现。从高位到低位对序列划分，实现排序。d是第几位数，d=1是最低位。left和right是待排序元素子序列的始端与尾端。 

141    int i, j, count[radix], p1, p2; 

142    int *auxArray; 

143    int M = 5; 

144    auxArray = new int[right-left+1]; 

145    if (d<=0) return; //位数处理完递归结束 

146    if (right-left+1<M){//对于小序列可调用直接插入排序 

147        InsertionSort(L,left,right); return; 

148    } 

149 for (j=0; j<radix; j++) count[j]=0; 

150    for (i=left; i<=right; i++) //统计各桶元素的存放位置 

151        count[getDigit(L[i],d)]++; 

152    for (j=1; j<radix; j++) //安排各桶元素的存放位置 

153        count[j]=count[j]+count[j-1]; 

154    for (i=right; i>=left; i--){ //将待排序序列中的元素按位置分配到各个桶中，存于助数组auxArray中 

155        j=getDigit(L[i],d);  //取元素L[i]第d位的值 

156        auxArray[count[j]-1]=L[i]; //按预先计算位置存放 

157        count[j]--;  //计数器减1 

158    } 

159    for (i=left, j=0; i<=right; i++, j++)  

160        L[i]=auxArray[j];  //从辅助数组顺序写入原数组 

161    delete []auxArray; 

162     for (j=0; j<radix; j++){ //按桶递归对d-1位处理 

163        p1=count[j]+left;  //取桶始端,相对位置，需要加上初值$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ 

164        (j+1 <radix )?(p2=count[j+1]-1+left):(p2=right) ; //取桶尾端 

165     //  delete []count; 

166        if(p1<p2){ 

167        RadixSort(L, p1, p2, d-1);  //对桶内元素进行基数排序  

168      //  printArray(L,10); 

169        } 

170    } 

171    

172 }  

173   

174 int getDigit(int num, int dig) 

175 { 

176     int myradix = 1; 

177 /*  for(int i = 1;i<dig;i++) 

178     { 

179     myradix *= radix; 

180     }*/

181     switch(dig) 

182     { 

183     case 1: 

184         myradix = 1; 

185         break; 

186 case 2: 

187         myradix = 10; 

188         break; 

189 case 3: 

190         myradix = 1000; 

191         break; 

192 case 4: 

193         myradix = 10000; 

194         break; 

195 default: 

196         myradix = 1; 

197         break; 

198     } 

199     return (num/myradix)%radix; 

200 }

maintest.cpp 测试例子：

view sourceprint?001 #include<iostream> 

002 using std::cout; 

003 using std::cin; 

004 using std::endl; 

005 #include <cstdlib> 

006 #include <ctime> 

007 #include<iostream> 

008 using std::cout; 

009 using std::cin; 

010 using std::ios; 

011 using std::cerr; 

012 using std::endl; 

013 #include<iomanip> 

014 using std::setw; 

015 using std::fixed; 

016 #include<fstream> 

017 using std::ifstream; 

018 using std::ofstream; 

019 using std::flush; 

020 #include<string> 

021 using std::string; 

022 #include <stdio.h> 

023 #include <stdlib.h> 

024 #include <time.h> 

025 #include"minheap.h" 

026 void BubbleSort(int arr[], int size);//冒泡排序 

027 void QuickSort( int A[], int startingsub, int endingsub);//快速排序 

028 void InsertionSort ( int L[], const int begin,const int n);//插入排序 

029 void Shellsort( int L[], const int left, const int right);//希尔排序 

030 void CountingSort( int L[], const int n );//计数排序 

031 int getDigit(int num, int dig);//基数排序中获取第dig位的数字 

032 void RadixSort(int L[], int left, int right, int d);//基数排序 

033 void printArray( const int Array[], const int arraySize );//输出数组 

034   

035 int main() 

036 { 

037     clock_t start, finish; 

038     double  duration; 

039     /* 测量一个事件持续的时间*/

040     ofstream *ofs; 

041     string fileName = "sortResult.txt"; 

042     ofs = new ofstream(fileName.c_str(),ios::out|ios::app); 

043     const int size = 100000; 

044     int a[size]; 

045     int b[size]; 

046     srand(time(0)); 

047     ofs->close(); 

048     for(int i = 0; i < 20;i++) 

049     { 

050         ofs->open(fileName.c_str(),ios::out|ios::app); 

051         if( ofs->fail()){ 

052                 cout<<"!!"; 

053                 ofs->close(); 

054         } 

055   

056         for(int k =0; k <size;k++) 

057         { 

058             a[k] = rand()%1000; 

059             b[k] = a[k]; 

060               

061         }        

062         /*  for( k =0; k <size;k++) 

063         { 

064         a[k] = k; 

065         b[k] = a[k]; 

066           

067     } */

068         //printArray(a,size);    

069         //计数排序 

070         for( k =0; k <size;k++) 

071         { 

072             a[k] =  b[k]; 

073         } 

074         start = clock(); 

075         CountingSort(a,size); 

076           

077         finish = clock(); 

078         //  printArray(a,size); 

079           

080         duration = (double)(finish - start) / CLOCKS_PER_SEC; 

081         printf( "%s%f seconds\n", "计数排序:",duration ); 

082         *ofs<<"第"<<i<<"次:\n " <<"排序内容：0~999共" << size <<  " 个整数\n" ; 

083         *ofs<<"第"<<i<<"次计数排序:\n " <<"       Time:   " <<fixed<< duration <<  " seconds\n"; 

084         //基数排序 

085         for( k =0; k <size;k++) 

086         { 

087             a[k] =  b[k]; 

088         } 

089         start = clock(); 

090         RadixSort(a, 0,size-1, 3); 

091         finish = clock(); 

092         //  printArray(a,size); 

093           

094         duration = (double)(finish - start) / CLOCKS_PER_SEC; 

095         printf( "%s%f seconds\n", "基数排序:",duration ); 

096         *ofs<<"第"<<i<<"次基数排序:\n " <<"       Time:   " << duration <<  " seconds\n"; 

097         //堆排序 

098         MinHeap<int> mhp(a,size);  

099         start = clock(); 

100         for( k =0; k <size;k++) 

101         { 

102             mhp.RemoveMin(a[k]); 

103         } 

104         finish = clock(); 

105         //  printArray(a,size); 

106         duration = (double)(finish - start) / CLOCKS_PER_SEC; 

107         printf( "%s%f seconds\n", "堆排序:",duration ); 

108         *ofs<<"第"<<i<<"次堆排序:\n " <<"        Time:   " << duration <<  " seconds\n"; 

109         //快速排序 

110         for( k =0; k <size;k++) 

111         { 

112             a[k] =  b[k]; 

113               

114         } 

115         //printArray(a,size); 

116         start = clock(); 

117         QuickSort(a,0,size-1); 

118         finish = clock(); 

119         //  printArray(a,size); 

120         duration = (double)(finish - start) / CLOCKS_PER_SEC; 

121         printf( "%s%f seconds\n", "快速排序:",duration ); 

122         *ofs<<"第"<<i<<"次快速排序:\n " <<"       Time:   " << duration <<  " seconds\n"; 

123   

124         //希尔排序 

125         for( k =0; k <size;k++) 

126         { 

127             a[k] =  b[k]; 

128         } 

129         start = clock(); 

130         Shellsort(a,0,size-1); 

131           

132         finish = clock(); 

133         //  printArray(a,size); 

134           

135         duration = (double)(finish - start) / CLOCKS_PER_SEC; 

136         printf( "%s%f seconds\n", "希尔排序:",duration ); 

137         *ofs<<"第"<<i<<"次希尔排序:\n " <<"       Time:   " << duration <<  " seconds\n"; 

138           

139         //插入排序 

140         for( k =0; k <size;k++) 

141         { 

142             a[k] =  b[k]; 

143         } 

144         start = clock(); 

145         InsertionSort (a,0,size-1); 

146         finish = clock(); 

147         //  printArray(a,size); 

148           

149         duration = (double)(finish - start) / CLOCKS_PER_SEC; 

150         printf( "%s%f seconds\n", "插入排序:",duration ); 

151         *ofs<<"第"<<i<<"次插入排序:\n " <<"       Time:   " << duration <<  " seconds\n"; 

152         //冒泡排序 

153         for( k =0; k <size;k++) 

154         { 

155             a[k] =  b[k]; 

156         } 

157         start = clock(); 

158         BubbleSort(a,size); 

159         finish = clock(); 

160         //  printArray(a,size); 

161           

162         duration = (double)(finish - start) / CLOCKS_PER_SEC; 

163         printf( "%s%f seconds\n", "冒泡排序:",duration ); 

164         *ofs<<"第"<<i<<"次冒泡排序:\n " <<"       Time:   " << duration <<  " seconds\n"; 

165   

166         ofs->close(); 

167         } 

168         return 0; 

169 } 

170   

171 void printArray( const int Array[], const int arraySize ) 

172 { 

173     for( int i = 0; i < arraySize; i++ ) { 

174         cout << Array[ i ] << "   "; 

175         if ( i % 20 == 19 ) 

176             cout << endl; 

177     } 

178     cout << endl; 

179 }

排序算法性能仿真：

排序内容：从0~999中随机产生，共100000 个整数，该表中单位为秒。



次数  计数排序  基数排序  堆排序  快速排序  希尔排序  直接插入排序  冒泡排序 
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