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

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

①插入排序

②折半插入排序

③選擇排序

④起泡排序

⑤快速排序

⑥希爾排序

⑦堆排序

⑧歸并排序

用随機數（介于1-100）産生10個待排序數據元素的關鍵字值）。

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

② 采用冒泡排序、快速排序方法對上述待排數據進行排序并輸出序後的有序序列；

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

④ 采用歸并排序方法對上述待排數據進行排序并輸出排序後的有序序列；

頭文件：

#include<cstdio> #include<iostream> #include<cstdlib> #define MAXSIZE 100 using 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<<"比較次數:"<<a<<"移動次數:"<<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); }

随機生成函數

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

輸出函數

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

（1）若n較小（例如n<50），可采用直接插入排序、冒泡排序或簡單選擇排序。如果記錄中的數據較多，移動較費時的，應采取簡單選擇排序法。

（2）若記錄的初始狀态已經按關鍵碼基本有序，則選用直接插入排序或冒泡排序法為宜。

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

（4）基數排序可在O (d×n) 時間内完成對n個記錄的排序，d是指單邏輯關鍵碼的個數，一般遠少于n。但基數排序隻适用于字符串和整數這類有明顯結構特征的關鍵碼。

（5）前面讨論的排序算法，除基數排序外，都是在順序存儲上實現的。當記錄本身的信息量很大時，為避免大量時間用在移動數據上，可以用鍊表作為存儲結構。插入排序和歸并排序都易在鍊表上實現，但有的排序方法，如快速排序和堆排序在鍊表上卻很難實現。

寫在最後：對于準備學習C/C 編程的小夥伴，如果你想更好的提升你的編程核心能力（内功）不妨從現在開始！

編程學習書籍分享：

編程學習視頻分享：

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

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

對于C/C 感興趣可以關注小編在後台私信我：【編程交流】一起來學習哦！可以領取一些C/C 的項目學習視頻資料哦！已經設置好了關鍵詞自動回複，自動領取就好了！

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!