多種排序演算法的C++實現（附圖）

一、Index

本文包含的排序演算法有

1、冒泡排序

2、歸併排序

3、插入排序

4、選擇排序

5、基數排序

6、快速排序

（更多排序演算法隨時更新）

二、代碼實現

代碼的功能：

1、對Index所列出的排序演算法的C++實現

2、可調整隨機數測試數組的大小，可以單獨/同時測試每個排序演算法，輸出排序所耗費的時間（單位：us）

#include <iostream>#include <time.h>using namespace std;const long datasize=1<<15;int arr[datasize]{};clock_t s,e;void print(int a[],long size);void BubbleSort(int a[],long size);void Merge(int arr[],long lo,long mi,long hi);void MergeSort(int arr[],long lo,long hi);void InsertSort(int arr[],long size);void SelectSort(int arr[],long size);void RadixSort(int arr[],long size);int Maxbit(int arr[],long size);void QuickSort(int arr[],long lo,long hi);int main(int argc, const char * argv[]) {#if 1 for(long i=0;i<datasize;i++) { arr[i]=rand(); } s=clock(); BubbleSort(arr, datasize); e=clock(); //print(arr,datasize); cout<<endl<<datasize<<" Num-Sortint "<<"BubbleSort Using: "<<e-s<<" us"<<endl;#endif #if 1 for(long i=0;i<datasize;i++) { arr[i]=rand(); } s=clock(); InsertSort(arr, datasize); e=clock(); //print(arr,datasize); cout<<endl<<datasize<<" Num-Sortint "<<"InsertSort Using: "<<e-s<<" us"<<endl;#endif #if 1 for(long i=0;i<datasize;i++) { arr[i]=rand(); } s=clock(); MergeSort(arr,0,datasize); e=clock(); //print(arr,datasize); cout<<endl<<datasize<<" Num-Sortint "<<"MergeSort Using: "<<e-s<<" us"<<endl;#endif #if 1 for(long i=0;i<datasize;i++) { arr[i]=rand(); } s=clock(); SelectSort(arr,datasize); e=clock(); //print(arr,datasize); cout<<endl<<datasize<<" Num-Sortint "<<"SelectSort Using: "<<e-s<<" us"<<endl;#endif #if 1 for(long i=0;i<datasize;i++) { arr[i]=rand(); } s=clock(); QuickSort(arr,0,datasize); e=clock(); //print(arr,datasize); cout<<endl<<datasize<<" Num-Sortint "<<"QuickSort Using: "<<e-s<<" us"<<endl;#endif #if 1 for(long i=0;i<datasize;i++) { arr[i]=rand(); } s=clock(); RadixSort(arr,datasize); e=clock(); //print(arr,datasize); //cout<<Maxbit(arr, datasize); cout<<endl<<datasize<<" Num-Sortint "<<"RadixSort Using: "<<e-s<<" us"<<endl;#endif }void BubbleSort(int a[],long size){ for(long i=0;i<size;i++) { bool flag=true; for(long j=0;j<size-i-1;j++) { if(a[j]>a[j+1]) { swap(a[j+1],a[j]); flag=false; } } if(true==flag)return; }}void MergeSort(int arr[],long lo,long hi){ if(hi-lo<2)return; long mi=(lo+hi)/2; MergeSort(arr,lo, mi); MergeSort(arr,mi, hi); Merge(arr,lo,mi,hi);}void Merge(int arr[],long lo,long mi,long hi){ long ml=mi-lo; int *b=new int[ml]; for(long i=0;i<ml;i++)b[i]=arr[lo+i]; //print(b, ml); long x=0,y=mi; for(long i=lo;i<hi { if((b[x]<=arr[y]&&x<ml)||y>=hi) { arr[i++]=b[x++]; } if((arr[y]<b[x]&&y<hi)||x>=ml) { arr[i++]=arr[y++]; } } delete []b;}void InsertSort(int arr[],long size){ for(int i=1;i<size;i++) { int temp=arr[i]; int j=i-1; while(j>=0) { if(arr[j]>temp)arr[j+1]=arr[j]; else break; j--; } arr[j+1]=temp; }}void SelectSort(int arr[],long size){ for(long i=size-1;i>=0;i--) { int maxnum=arr[i]; long rank=i; for(long j=0;j<i;j++) { if(arr[j]>=maxnum) { maxnum=arr[j]; rank=j; } } swap(arr[rank], arr[i]); }}void QuickSort(int arr[],long lo,long hi){ if(hi-lo<2)return; long rank=rand()%(hi-lo)+lo,ranklo=lo,rankhi=hi; swap(arr[ranklo],arr[rank]); int key=arr[lo]; hi--; while(lo<hi) { while(lo<hi&&key<=arr[hi])hi--; arr[lo]=arr[hi]; while(lo<hi&&arr[lo]<=key)lo++; arr[hi]=arr[lo]; } arr[lo]=key; QuickSort(arr, ranklo,lo); QuickSort(arr, lo+1,rankhi);}void RadixSort(int arr[],long size){ int bit=Maxbit(arr, size); int radix=1; int *tmp=new int[size]; int *countn=new int[10]; while(bit--) { for(int i=0;i<10;i++) { countn[i]=0; } for(int i=0;i<size;i++) { int k=(arr[i]/radix)%10; countn[k]++; } for(int i=1;i<10;i++) { countn[i]+=countn[i-1]; } for(int i=0;i<size;i++) { int k=(arr[i]/radix)%10; tmp[countn[k]-1]=arr[i]; countn[k]--; } for(int i=0;i<size;i++) { arr[i]=tmp[i]; } radix*=10; } delete []tmp; tmp=NULL; delete []countn; countn=NULL;}int Maxbit(int arr[],long size){ int maxnum=0; for(int i=0;i<size;i++) { if(arr[i]>maxnum)maxnum=arr[i]; } //cout<<maxnum<<endl; int bit=0; while(maxnum) { maxnum/=10; bit++; } return bit;}void print(int a[],long size){ for(long i=0;i<size;i++) { cout<<a[i]<<" "; if(0==i+1%4)cout<<endl; }}

三、測試

輸入：

無

輸出：

32768 Num-Sortint BubbleSort Using: 5174296 us 32768 Num-Sortint InsertSort Using: 1103438 us 32768 Num-Sortint MergeSort Using: 10770 us 32768 Num-Sortint SelectSort Using: 1706316 us 32768 Num-Sortint QuickSort Using: 6801 us 32768 Num-Sortint RadixSort Using: 7835 us

四、排序演算法圖示以及原理說明

冒泡排序

複雜度：O(n^2)

1、對數組array[n]進行從0~n-1項的掃描，每碰到相鄰兩項數值大的在前小的在後時，對二者進行交換。當掃描進行完成後，0~n-1中最大的元素必然已經在array[n-1]就位，而所有數值較小，序號卻靠後的元素，序號也減小了1。

2、既然最大的元素已在array[n-1]的位置就位，接下來的掃描只需從0~n-2。具體過程同1。同樣的，掃描結束後0~n-2中最大的元素（全數組第二大的元素）必然已經在array[n-2]就位，而所有數值較小，序號卻靠後的元素，序號也減小了1。

3、如此不斷重複，直到最小的元素在array[0]的位置就位。

從上述描述中我們可以看到「冒泡排序」這個名字的由來：每一次掃描，都可以使得數值較小，序號卻靠後的元素的序號減少1，宏觀來看這些元素就像是從數組底部向上慢慢上浮的泡泡。

插入排序

複雜度：O(n^2)

插入排序和人們打牌時所用的排序方式類似：

1、抽第一張牌，此時手上的牌只有一張，所以是有序的。

2、再抽一張牌，和手上的那張牌的大小進行比較，比它大就放在後面，否則放在前面。

3、再抽一張牌，和手上的牌進行比較，插入在合適的位置，保持手上的牌有序。

4、不斷重複3，直到牌抽完。

從宏觀來看，插入排序把數組分割成兩部分，前段有序後段無序，隨著插入排序的進行，後段無序的牌也越來越少，直到後段全部融入前段，排序也就結束了。

歸併排序

複雜度：O(nlogn)

歸併排序的操作有兩步，分割和歸併

1、分割：將數組二等分，並將得到的子數組繼續二等分，直到每個子數組只剩下一個元素為止。

2、歸併：不斷將原本屬於同一個數組的兩個子數組歸併成一個有序的數組，方法為不斷比較子數組的首元素，並彈出較小的放入合併後組成的數組中。直到所有子數組合併為一個數組。

選擇排序

複雜度：O(n^2)

1、從數組中找出最小的元素，找出來後，將其和數組首元素互換位置。

2、此時待排序的數組規模-1。對這個規模減小的數組進行步驟1、直到待排序的數組規模為0。

快速排序

複雜度：O(n^2) （最壞情況）O(nlogn)（平均情況）

1、從數組中隨機選出一個元素，和數組首元素互換位置，並記下其大小。

2、使用兩個指針，指針a指向數組頭，指針b指向數組尾。

3、指針b從後向前掃描，找到一個數比選出元素小時，暫停，將其值保存在指針a所指的位置中。

4、指針a從前往後掃描，找到一個數比選出元素大時，暫停，將其值保存在指針b所指的位置中。

5、循環重複3、4，直到a<b不再成立。

6、將選出元素放在指針a、b同時指向的位置，並用此位置將數組分割成前後不包含選出元素的兩個子數組，對子數組進行步驟1~6。

PS：

廣告時間啦~

理工狗不想被人文素養拖後腿？不妨關注微信公眾號：

為你讀最好的書~