為了讓大家掌握多種排序方法的基本思想，本篇文章帶著大家對數(shù)據(jù)結(jié)構(gòu)的常用七大算法進行分析：包括直接插入排序、希爾排序、冒泡排序、快速排序、簡單選擇排序、堆排序、歸并排序等，并能夠用高級語言實現(xiàn)。

希望通過對這些算法效率的比較，加深對算法的理解。

①插入排序

②折半插入排序

③選擇排序

④起泡排序

⑤快速排序

⑥希爾排序

⑦堆排序

⑧歸并排序

排序算法的分析圖解：

用隨機數(shù)（介于1-100）產(chǎn)生10個待排序數(shù)據(jù)元素的關(guān)鍵字值）。

① 采用直接插入排序和希爾排序方法對上述待排數(shù)據(jù)進行排序并輸出序后的有序序列；

② 采用冒泡排序、快速排序方法對上述待排數(shù)據(jù)進行排序并輸出序后的有序序列；

③ 采用簡單選擇排序、堆排序方法對上述待排數(shù)據(jù)進行排序并輸出序后的有序序列；

④ 采用歸并排序方法對上述待排數(shù)據(jù)進行排序并輸出排序后的有序序列；

代碼分析

頭文件：

#include<cstdio>#include<iostream>#include<cstdlib>#define MAXSIZE 100using namespace std;typedef int KeyType;typedef int InfoType;typedef struct{ KeyType key; InfoType otherinfo;}RedType;typedef struct{ RedType r[MAXSIZE+1]; int length;}SqList;

①插入排序

void InsertSort(SqList &L){ int i,j,a=0,b=0; for(i=1;i<=L.length;++i) { if(L.r[i].key<L.r[i-1].key) { L.r[0]=L.r[i]; L.r[i]=L.r[i-1]; a++; } for(j=i-2;L.r[0].key<L.r[j].key;--j) L.r[j+1]=L.r[j];b++; L.r[j+1]=L.r[0]; } cout<<"比較次數(shù):"<<a<<"移動次數(shù):"<<b<<endl;}

②折半插入排序

void BInsertSort(SqList &L){ int low,high,m; for(int i=2;i<=L.length;++i) { L.r[0]=L.r[i]; low=1;high=i-1; while(low<=high) { m=(low+high)/2; if(L.r[0].key<L.r[m].key)high=m-1; else low=m+1; } for(int j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; L.r[high+1]=L.r[0]; }}

③選擇排序

void SelectSort(SqList &L){ int j,k; for(int i=1;i<=L.length;++i) { k=i; for(j=i+1;j<=L.length;j++) if(L.r[j].key<L.r[k].key)k=j; if(k!=i) { L.r[0].key=L.r[i].key; L.r[i].key=L.r[k].key; L.r[k].key=L.r[0].key; } }}

④起泡排序

void BubbleSort(SqList &L){ int i,j; for(i=1;i<=L.length;++i) { for(j=1;j<L.length-i+1;++j) { if(L.r[j+1].key<L.r[j].key) { L.r[0].key=L.r[j].key; L.r[j].key=L.r[j+1].key; L.r[j+1].key=L.r[0].key; } } }}

⑤快速排序

int Partition(SqList &L,int low,int high){ L.r[0]=L.r[low]; KeyType pivotkey=L.r[low].key; while(low<high) { while(low<high&&L.r[high].key>=pivotkey)--high; L.r[low]=L.r[high]; while(low<high&&L.r[low].key<=pivotkey)++low; L.r[high]=L.r[low]; } L.r[low]=L.r[0]; return low;}void QSort(SqList &L,int low,int high){ if(low<high) { int pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); }}

⑥希爾排序

void ShellInsert(SqList &L,int dk){ int i,j; for(i=dk+1;i<=L.length;++i) { if(L.r[i].key<L.r[i-dk].key){L.r[0]=L.r[i]; for(j=i-dk;j>0&&L.r[0].key<L.r[j].key;j-=dk) L.r[j+dk]=L.r[j]; L.r[j+dk]=L.r[0]; } }}void ShellSort(SqList &L,int dlta[],int t){ for(int k=0;k<t;++k) ShellInsert(L,dlta[k]);}

⑦堆排序

typedef SqList HeapType;void HeapAdjust(HeapType &H,int s,int m){ RedType rc=H.r[s];int j; for(j=2*s;j<=m;j*=2) { if(j<m&&H.r[j].key<H.r[j+1].key)++j; if(!(rc.key<H.r[j].key))break; H.r[s]=H.r[j];s=j; } H.r[s]=rc;}void HeapSort(HeapType &H){ int i; RedType temp; for(i=H.length/2;i>0;--i) HeapAdjust(H,i,H.length); for(i=H.length;i>1;--i) { temp=H.r[1]; H.r[1]=H.r[i]; H.r[i]=temp; HeapAdjust(H,1,i-1); }

⑧歸并排序

void Merge(RedType SR[],RedType &TR[],int i,int m,int n){ int j,k; for(j=m+1,k=i;i<=m&&j<=n;++k) { if(SR[i].key<=SR[j].key) TR[k]=SR[i++]; else TR[k]=SR[j++]; } int t; if(i<=m) { for(t=i;t<=m;t++) TR[k+t-i]=SR[t]; } if(j<=n) { for(t=j;t<=m;t++) TR[k+t-j]=SR[t]; }}void MSort(RedType SR[],RedType *TR1,int s,int t){ int m; RedType TR2[MAXSIZE+1]; if(s==t)TR1[s]=SR[s]; else{ m=(s+t)/2; MSort(SR,TR2,s,m); MSort(SR,TR2,m+1,t); Merge(TR2,TR1,s,m,t); }}void MergeSort(SqList &L){ MSort(L.r,L.r,1,L.length);}

隨機生成函數(shù)

void RandSqList(SqList &L){ int n,max,min; printf("輸入順序表的大小\n"); cin>>n; printf("輸入最小值和最大值\n"); cin>>min>>max; L.length=n; printf("隨機產(chǎn)生%d個數(shù)\n",n); for(int i=1;i<=L.length;++i) { L.r[i].key=rand()%(max-min+1); L.r[i].key+=min; } printf("順序表創(chuàng)建成功!\n");}

輸出函數(shù)

void Output(SqList L){ printf("輸出：\n"); for(int i=1;i<=L.length;i++) cout<<"data"<<"["<<i<<"]"<<": "<<L.r[i].key<<endl;}結(jié)論

（1）若n較?。ɡ鏽<50），可采用直接插入排序、冒泡排序或簡單選擇排序。如果記錄中的數(shù)據(jù)較多，移動較費時的，應采取簡單選擇排序法。

（2）若記錄的初始狀態(tài)已經(jīng)按關(guān)鍵碼基本有序，則選用直接插入排序或冒泡排序法為宜。

（3）若n較大，則應采用改進排序方法，如快速排序、堆排序或歸并排序法。這些排序算法的時間復雜度均為O(nlog2n)，但就平均性能而言，快速排序被認為是目前基于比較記錄關(guān)鍵碼的內(nèi)部排序中最好的排序方法，但遺憾的是，快速排序在最壞情況下的時間復雜度是O(n2)，堆排序與歸并排序的最壞情況時間復雜度仍為O(nlog2n)。堆排序和快速排序法都是不穩(wěn)定的排序。若要求穩(wěn)定排序，則可選用歸并排序。

（4）基數(shù)排序可在O (d×n) 時間內(nèi)完成對n個記錄的排序，d是指單邏輯關(guān)鍵碼的個數(shù)，一般遠少于n。但基數(shù)排序只適用于字符串和整數(shù)這類有明顯結(jié)構(gòu)特征的關(guān)鍵碼。

（5）前面討論的排序算法，除基數(shù)排序外，都是在順序存儲上實現(xiàn)的。當記錄本身的信息量很大時，為避免大量時間用在移動數(shù)據(jù)上，可以用鏈表作為存儲結(jié)構(gòu)。插入排序和歸并排序都易在鏈表上實現(xiàn)，但有的排序方法，如快速排序和堆排序在鏈表上卻很難實現(xiàn)。

寫在最后：對于準備學習C/C++編程的小伙伴，如果你想更好的提升你的編程核心能力（內(nèi)功）不妨從現(xiàn)在開始！

編程學習書籍分享：

編程學習視頻分享：

整理分享（多年學習的源碼、項目實戰(zhàn)視頻、項目筆記，基礎(chǔ)入門教程）

歡迎轉(zhuǎn)行和學習編程的伙伴，利用更多的資料學習成長比自己琢磨更快哦！

對于C/C++感興趣可以關(guān)注小編在后臺私信我：【編程交流】一起來學習哦！可以領(lǐng)取一些C/C++的項目學習視頻資料哦！已經(jīng)設(shè)置好了關(guān)鍵詞自動回復，自動領(lǐng)取就好了！