各种排序算法的C++实现
這篇文章的源碼是大二時(shí)數(shù)據(jù)結(jié)構(gòu)課的實(shí)驗(yàn)。當(dāng)時(shí)的實(shí)驗(yàn)?zāi)康氖潜容^各種排序算法的性能。現(xiàn)在感覺其中的排序源碼還比較有用，就貼出來了。
minheap.h 用于堆排序
?
//使用時(shí)注意將關(guān)鍵碼加入 #ifndef MINHEAP_H #define MINHEAP_H #include <assert.h> #include <iostream> using std::cout; using std::cin; using std::endl; using std::cerr; #include <stdlib.h> //const int maxPQSize = 50; template <class Type> class MinHeap { public: MinHeap ( int maxSize );//根據(jù)最大長度建堆MinHeap ( Type arr[], int n );//根據(jù)數(shù)組arr[]建堆~MinHeap ( ) { delete [] heap; }const MinHeap<Type> & operator = ( const MinHeap &R );//重載賦值運(yùn)算符int Insert ( const Type &x );//插入元素int RemoveMin ( Type &x );//移除關(guān)鍵碼最小的元素，并賦給xint IsEmpty ( ) const { return CurrentSize == 0; }//檢查堆是否為空 int IsFull ( ) const { return CurrentSize == MaxHeapSize; }//檢查對是否滿void MakeEmpty ( ) { CurrentSize = 0; }//使堆空 private: enum { DefaultSize = 50 };//默認(rèn)堆的大小Type *heap; int CurrentSize;int MaxHeapSize;void FilterDown ( int i, int m );//自上向下調(diào)整堆void FilterUp ( int i );//自下向上調(diào)整堆 };template <class Type> MinHeap <Type>::MinHeap ( int maxSize ) {//根據(jù)給定大小maxSize,建立堆對象MaxHeapSize = (DefaultSize < maxSize ) ? maxSize : DefaultSize; //確定堆大小heap = new Type [MaxHeapSize]; //創(chuàng)建堆空間CurrentSize = 0; //初始化 }template <class Type> MinHeap <Type>::MinHeap ( Type arr[], int n ) {//根據(jù)給定數(shù)組中的數(shù)據(jù)和大小,建立堆對象 MaxHeapSize = DefaultSize < n ? n : DefaultSize;heap = new Type [MaxHeapSize]; if(heap==NULL){cerr <<"fail" <<endl;exit(1);}for(int i =0; i< n; i++)heap[i] = arr[i]; //數(shù)組傳送CurrentSize = n; //當(dāng)前堆大小int currentPos = (CurrentSize-2)/2; //最后非葉while ( currentPos >= 0 ) { //從下到上逐步擴(kuò)大,形成堆FilterDown ( currentPos, CurrentSize-1 );currentPos-- ;//從currentPos開始,到0為止, 調(diào)整currentPos--; }} }template <class Type> void MinHeap<Type>::FilterDown ( const int start, const int EndOfHeap ) {// 結(jié)點(diǎn)i的左、右子樹均為堆，調(diào)整結(jié)點(diǎn)iint i = start, j = 2*i+1; // j 是 i 的左子女Type temp = heap[i];while ( j <= EndOfHeap ) {if ( j < EndOfHeap && heap[j] > heap[j+1] )j++;//兩子女中選小者if ( temp<= heap[j] ) break;else { heap[i] = heap[j]; i = j; j = 2*j+1; }}heap[i] = temp; }template <class Type> int MinHeap<Type>::Insert ( const Type &x ) {//在堆中插入新元素 xif ( CurrentSize == MaxHeapSize ) //堆滿{ cout << "堆已滿" << endl; return 0; }heap[CurrentSize] = x; //插在表尾 FilterUp (CurrentSize); //向上調(diào)整為堆CurrentSize++; //堆元素增一return 1; }template <class Type> void MinHeap<Type>::FilterUp ( int start ) {//從 start 開始,向上直到0,調(diào)整堆int j = start, i = (j-1)/2; // i 是 j 的雙親Type temp = heap[j];while ( j > 0 ) { if ( (heap[i].root->data.key )<= (temp.root->data.key) ) break;else { heap[j] = heap[i]; j = i; i = (i -1)/2; }}heap[j] = temp; } template <class Type> int MinHeap <Type>::RemoveMin ( Type &x ) {if ( !CurrentSize ){ cout << "堆已空 " << endl; return 0; }x = heap[0]; //最小元素出隊(duì)列heap[0] = heap[CurrentSize-1]; CurrentSize--; //用最小元素填補(bǔ)FilterDown ( 0, CurrentSize-1 );//從0號(hào)位置開始自頂向下調(diào)整為堆return 1; } #endifsort.cpp 主要的排序函數(shù)集包括冒泡排序、快速排序、插入排序、希爾排序、計(jì)數(shù)排序
?
?
//n^2 //冒泡排序V[n]不參與排序 void BubbleSort (int V[], int n ) {bool exchange; //設(shè)置交換標(biāo)志置for ( int i = 0; i < n; i++ ){exchange=false;for (int j=n-1; j>i; j--) { //反向檢測，檢查是否逆序if (V[j-1] > V[j]) //發(fā)生逆序，交換相鄰元素{ int temp=V[j-1]; V[j-1]=V[j];V[j]=temp; exchange=true;//交換標(biāo)志置位}}if (exchange == false)return; //本趟無逆序，停止處理} }//插入排序,L[begin],L[end]都參與排序 void InsertionSort ( int L[], const int begin, const int end) {//按關(guān)鍵碼 Key 非遞減順序?qū)Ρ磉M(jìn)行排序int temp;int i, j;for ( i = begin; i < end; i++ ) {if (L[i]>L[i+1]) {temp = L[i+1]; j=i;do {L[j+1]=L[j];if(j == 0){j--;break;}j--;} while(temp<L[j]);L[j+1]=temp;}} } //n*logn //快速排序A[startingsub],A[endingsub]都參與排序 void QuickSort( int A[], int startingsub, int endingsub) {if ( startingsub >= endingsub );else{int partition;int q = startingsub;int p = endingsub;int hold;do{for(partition = q ; p > q ; p--){if( A[q] > A[p]){hold = A[q];A[q] = A[p];A[p] = hold;break;}}for(partition = p; p > q; q++){if(A[p] < A[q]){hold = A[q];A[q] = A[p];A[p] = hold;break;}}}while( q < p );QuickSort( A, startingsub, partition - 1 );QuickSort( A, partition + 1, endingsub );} }//希爾排序,L[left],L[right]都參與排序 void Shellsort( int L[], const int left, const int right) {int i, j, gap=right-left+1; //增量的初始值int temp;do{gap=gap/3+1; //求下一增量值for(i=left+gap; i<=right; i++)//各子序列交替處理if( L[i]<L[i-gap]){ //逆序temp=L[i]; j=i-gap; do{L[j+gap]=L[j]; //后移元素j=j-gap; //再比較前一元素}while(j>left&&temp<L[j]);L[j+gap]=temp; //將vector[i]回送}}while(gap>1); } //n //計(jì)數(shù)排序,L[n]不參與排序 void CountingSort( int L[], const int n ) {int i,j;const int k =1001;int tmp[k];int *R;R = new int[n];for(i=0;i<k;i++) tmp[i]= 0; for(j=0;j<n;j++) tmp[L[j]]++; //執(zhí)行完上面的循環(huán)后，tmp[i]的值是L中等于i的元素的個(gè)數(shù)for(i=1;i<k;i++)tmp[i]=tmp[i]+tmp[i-1]; //執(zhí)行完上面的循環(huán)后，//tmp[i]的值是L中小于等于i的元素的個(gè)數(shù)for(j=n-1;j>=0;j--) //這里是逆向遍歷，保證了排序的穩(wěn)定性{R[tmp[L[j]]-1] = L[j]; //L[j]存放在輸出數(shù)組R的第tmp[L[j]]個(gè)位置上tmp[L[j]]--; //tmp[L[j]]表示L中剩余的元素中小于等于L[j]的元素的個(gè)數(shù) }for(j=0;j<n;j++) L[j] = R[j]; }//基數(shù)排序 void printArray( const int Array[], const int arraySize ); int getDigit(int num, int dig); const int radix=10; //基數(shù) void RadixSort(int L[], int left, int right, int d){ //MSD排序算法的實(shí)現(xiàn)。從高位到低位對序列劃分，實(shí)現(xiàn)排序。d是第幾位數(shù)，d=1是最低位。left和right是待排序元素子序列的始端與尾端。int i, j, count[radix], p1, p2;int *auxArray;int M = 5;auxArray = new int[right-left+1];if (d<=0) return; //位數(shù)處理完遞歸結(jié)束if (right-left+1<M){//對于小序列可調(diào)用直接插入排序InsertionSort(L,left,right); return;} for (j=0; j<radix; j++) count[j]=0;for (i=left; i<=right; i++) //統(tǒng)計(jì)各桶元素的存放位置count[getDigit(L[i],d)]++;for (j=1; j<radix; j++) //安排各桶元素的存放位置count[j]=count[j]+count[j-1];for (i=right; i>=left; i--){ //將待排序序列中的元素按位置分配到各個(gè)桶中，存于助數(shù)組auxArray中j=getDigit(L[i],d); //取元素L[i]第d位的值auxArray[count[j]-1]=L[i]; //按預(yù)先計(jì)算位置存放count[j]--; //計(jì)數(shù)器減1}for (i=left, j=0; i<=right; i++, j++) L[i]=auxArray[j]; //從輔助數(shù)組順序?qū)懭朐瓟?shù)組delete []auxArray;for (j=0; j<radix; j++){ //按桶遞歸對d-1位處理p1=count[j]+left; //取桶始端,相對位置，需要加上初值$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$(j+1 <radix )?(p2=count[j+1]-1+left):(p2=right) ; //取桶尾端// delete []count;if(p1<p2){RadixSort(L, p1, p2, d-1); //對桶內(nèi)元素進(jìn)行基數(shù)排序 // printArray(L,10);}}} int getDigit(int num, int dig) {int myradix = 1; /* for(int i = 1;i<dig;i++){myradix *= radix;}*/switch(dig){case 1:myradix = 1;break; case 2:myradix = 10;break; case 3:myradix = 1000;break; case 4:myradix = 10000;break; default:myradix = 1;break;}return (num/myradix)%radix; }maintest.cpp 測試?yán)?/p>
?
#include<iostream> using std::cout; using std::cin; using std::endl; #include <cstdlib> #include <ctime> #include<iostream> using std::cout; using std::cin; using std::ios; using std::cerr; using std::endl; #include<iomanip> using std::setw; using std::fixed; #include<fstream> using std::ifstream; using std::ofstream; using std::flush; #include<string> using std::string; #include <stdio.h> #include <stdlib.h> #include <time.h> #include"minheap.h" void BubbleSort(int arr[], int size);//冒泡排序 void QuickSort( int A[], int startingsub, int endingsub);//快速排序 void InsertionSort ( int L[], const int begin,const int n);//插入排序 void Shellsort( int L[], const int left, const int right);//希爾排序 void CountingSort( int L[], const int n );//計(jì)數(shù)排序 int getDigit(int num, int dig);//基數(shù)排序中獲取第dig位的數(shù)字 void RadixSort(int L[], int left, int right, int d);//基數(shù)排序 void printArray( const int Array[], const int arraySize );//輸出數(shù)組int main() {clock_t start, finish;double duration;/* 測量一個(gè)事件持續(xù)的時(shí)間*/ofstream *ofs;string fileName = "sortResult.txt";ofs = new ofstream(fileName.c_str(),ios::out|ios::app);const int size = 100000;int a[size];int b[size];srand(time(0));ofs->close();for(int i = 0; i < 20;i++){ofs->open(fileName.c_str(),ios::out|ios::app);if( ofs->fail()){cout<<"!!";ofs->close();}for(int k =0; k <size;k++){a[k] = rand()%1000;b[k] = a[k];} /* for( k =0; k <size;k++){a[k] = k;b[k] = a[k];} *///printArray(a,size); //計(jì)數(shù)排序for( k =0; k <size;k++){a[k] = b[k];}start = clock();CountingSort(a,size);finish = clock();// printArray(a,size);duration = (double)(finish - start) / CLOCKS_PER_SEC;printf( "%s%f seconds\n", "計(jì)數(shù)排序:",duration );*ofs<<"第"<<i<<"次:\n " <<"排序內(nèi)容：0~999共" << size << " 個(gè)整數(shù)\n" ;*ofs<<"第"<<i<<"次計(jì)數(shù)排序:\n " <<" Time: " <<fixed<< duration << " seconds\n";//基數(shù)排序for( k =0; k <size;k++){a[k] = b[k];}start = clock();RadixSort(a, 0,size-1, 3);finish = clock();// printArray(a,size);duration = (double)(finish - start) / CLOCKS_PER_SEC;printf( "%s%f seconds\n", "基數(shù)排序:",duration );*ofs<<"第"<<i<<"次基數(shù)排序:\n " <<" Time: " << duration << " seconds\n";//堆排序MinHeap<int> mhp(a,size); start = clock();for( k =0; k <size;k++){mhp.RemoveMin(a[k]);}finish = clock();// printArray(a,size);duration = (double)(finish - start) / CLOCKS_PER_SEC;printf( "%s%f seconds\n", "堆排序:",duration );*ofs<<"第"<<i<<"次堆排序:\n " <<" Time: " << duration << " seconds\n";//快速排序for( k =0; k <size;k++){a[k] = b[k];}//printArray(a,size);start = clock();QuickSort(a,0,size-1);finish = clock();// printArray(a,size);duration = (double)(finish - start) / CLOCKS_PER_SEC;printf( "%s%f seconds\n", "快速排序:",duration );*ofs<<"第"<<i<<"次快速排序:\n " <<" Time: " << duration << " seconds\n";//希爾排序for( k =0; k <size;k++){a[k] = b[k];}start = clock();Shellsort(a,0,size-1);finish = clock();// printArray(a,size);duration = (double)(finish - start) / CLOCKS_PER_SEC;printf( "%s%f seconds\n", "希爾排序:",duration );*ofs<<"第"<<i<<"次希爾排序:\n " <<" Time: " << duration << " seconds\n";//插入排序for( k =0; k <size;k++){a[k] = b[k];}start = clock();InsertionSort (a,0,size-1);finish = clock();// printArray(a,size);duration = (double)(finish - start) / CLOCKS_PER_SEC;printf( "%s%f seconds\n", "插入排序:",duration );*ofs<<"第"<<i<<"次插入排序:\n " <<" Time: " << duration << " seconds\n";//冒泡排序for( k =0; k <size;k++){a[k] = b[k];}start = clock();BubbleSort(a,size);finish = clock();// printArray(a,size);duration = (double)(finish - start) / CLOCKS_PER_SEC;printf( "%s%f seconds\n", "冒泡排序:",duration );*ofs<<"第"<<i<<"次冒泡排序:\n " <<" Time: " << duration << " seconds\n";ofs->close();}return 0; }void printArray( const int Array[], const int arraySize ) {for( int i = 0; i < arraySize; i++ ) {cout << Array[ i ] << " ";if ( i % 20 == 19 )cout << endl;}cout << endl; }最后貼一下運(yùn)行結(jié)果和當(dāng)時(shí)的實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果
?
| 實(shí)驗(yàn)結(jié)果 排序算法性能仿真 | |||||||
| ?排序內(nèi)容：從0~999中隨機(jī)產(chǎn)生，共100000 個(gè)整數(shù)，該表中單位為秒 | |||||||
| 次數(shù) | 計(jì)數(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 |
轉(zhuǎn)載于:https://www.cnblogs.com/allen8807/archive/2010/11/17/1879613.html
總結(jié)
以上是生活随笔為你收集整理的各种排序算法的C++实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： ACT5.6 动手实验手册 如何在工作组
- 下一篇： 为什么人生气时说话用喊的