目錄

前言

1.冒泡排序

2.直接插入排序

3.希爾排序

4.直接選擇排序

5.堆排序

6.快速排序

6.1將區間按照基準值劃分為左右兩半部分的常見方式

6.1.1Hoare版本

6.1.2挖坑法

6.1.3前后指針法

6.2快速排序的優化

6.2.1針對有序數組快排效率較低進行優化

6.2.2小區間優化

前言

排序是我們程序員在編程中常常要接觸到的知識，所以它非常重要，常見的排序算法有插入排序，選擇排序，交換排序，歸并排序......今天我們就來實現一下這幾種排序的c語言代碼，以及對比一下這幾種排序的優劣。

1.冒泡排序

冒泡排序是我接觸過的第一種排序方法，也是最簡單的，當然也是時間復雜度非常高的（意味著它比較垃圾哈哈哈）。以升序為例，它的原理是：

1、從左至右遍歷對比相鄰兩個元素的大小，將數組最大的元素推到最右邊以實現升序。

2、接著數組排序個數減去1（減一是因為已經排序好的最大的元素），開始找出次大的元素。

3、重復上面的兩個過程直到排序個數為0，就實現了升序排序。

單趟排序原理圖：

代碼實現如下：

void BubbleSort(int* a, int n) {//遍歷所有數for (int i = 0; i < n; i++){//定義一個exchange判斷是否發生交換int exchange = 0;//單趟排序for (int j = 1; j < n - i; j++){//升序，如果前一個大于后一個，就交換if (a[j - 1] > a[j]){exchange = 1;Swap(&a[j - 1], &a[j]);}}//exchange為0，說明沒有交換，跳出循環，防止消耗內存資源if (exchange == 0){break;}} }

2.直接插入排序

直接插入排序是一種簡單的插入排序法，其基本思想是：

把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。

實際中我們玩打斗地主理牌時，就用了插入排序的思想：

?直接插入排序原理圖：

直接插入排序代碼實現：

// 直接插入排序 void InsertSort(int* a, int n) {//遍歷每個數,end為每個區間的右邊緣for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];//要插入的數為tmpwhile (end >= 0){//升序，如果要插入的數小于a[end]，就把這個值往后挪，隨后繼續比較a[end-1]...if (tmp < a[end]){a[end+1] = a[end];end--;}else{break;}}a[end + 1] = tmp;} }

3.希爾排序

希爾排序法是直接插入排序的一種優化，他的思想是先對數據進行預排序，即大致分成左邊較小，右邊較大的一組數據，然后在進行插入排序，具體的步驟如下：
1、定義一個值gap，即步長，將數據間隔gap分為幾組。

2、對分成的這幾組數據分別進行插入排序，即完成預排序。

3、然后進行插入排序（間隔gap=1）。

原理圖如下：

?代碼實現如下：

// 希爾排序 void ShellSort(int* a, int n) {int gap = n;while (gap > 1){gap = gap / 3 + 1;//逐步減小gap,最后gap會為1for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];//要插入的數為tmpwhile (end >= 0){//升序，如果后一個數小于前一個，就將前一個的值賦給后一個if (tmp < a[end]){a[end + gap] = a[end];end = end-gap;}else{break;}}a[end + gap] = tmp;}} }

4.直接選擇排序

直接選擇排序比較暴力，其基本原理是：

每一次從待排序的數據元素中選出最小和最大的一個元素，存放在序列的起始位置和末尾位置，直到全部待排序的數據元素排完。

原理圖如下：

代碼實現如下：

// 選擇排序 void SelectSort(int* a, int n) {int left = 0;int right = n - 1;while (left < right){int mini = left;int maxi = right;for (int i = left + 1; i <= right; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[left],&a[mini]);//如果left和maxi重疊，就會掉包掉最大的值，所以要防被掉包if (maxi == left)//left 和 maxi 重疊，最大值被換到了下標mini上{maxi = mini;}Swap(&a[right], &a[maxi]);left++;right--;} }

5.堆排序

堆排序的原理就是在數組上建堆，實現升序建立大堆，實現降序建立小堆，接著使用向下調整算法及堆刪除思想實現排序。具體的實現代碼和原理可以看我的前兩期博客

堆排序算法

為什么升序建立大堆，降序建立小堆

6.快速排序

終于到了本期博客的重頭戲了，快速排序是一種非常NB的排序，難怪C語言的庫函數qsort的原理也是快速排序，快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。

//假設按照升序對array數組中[left, right]區間中的元素進行排序 void QuickSort1(int* a, int left, int right) { //遞歸結束條件，當區間不存在時就停止遞歸if (left >= right){return;}//按照基準值對array數組的 [left, right)區間中的元素進行劃分int keyi = PartSort1(a, left, right);//劃分成功后以keyi為邊界形成了左右兩部分 [left, key-1] 和 [key+1, right] //[left,keyi-1] keyi [keyi+1,right]//遞歸排[left,keyi-1] QuickSort1(a, left, keyi-1); //遞歸排[keyi+1,right]QuickSort1(a, keyi+1, right);}

上述為快速排序遞歸實現的主框架，發現與二叉樹前序遍歷規則非常像，我們在寫遞歸框架時可想想二叉樹前序遍歷規則即可快速寫出來，后序只需分析如何按照基準值來對區間中數據進行劃分的方式即可。

//快速排序非遞歸實現大框架 void QuickSortNonR(int* a, int left, int right) {Stack ST;//創建一個棧StackInit(&ST);//初始化棧StackPush(&ST, left);//左區間入棧StackPush(&ST, right);//右區間入棧while (!StackEmpty(&ST))//當棧不為空時進入循環{int right = StackTop(&ST);StackPop(&ST);int left = StackTop(&ST);StackPop(&ST);int keyi = PartSort3(a, left, right);//[left,keyi-1] keyi [keyi+1,right]///*if (left >= right){return;}*///這一步的if判斷相當于遞歸實現中上面的部分if (left < keyi - 1)//如果區間存在,不寫小于<=是因為left = right時候只有一個數，不需要排序{StackPush(&ST, left);//左區間入棧StackPush(&ST, keyi-1);//右區間入棧}if (keyi+1 < right){StackPush(&ST, keyi+1);//左區間入棧StackPush(&ST, right);//右區間入棧}}StackDestroy(&ST);//銷毀棧，防止內存泄漏}

上述為快速排序非遞歸實現的主框架，我們是利用棧的特性去實現的，當一個算法是使用遞歸去實現時，如果要改成非遞歸實現，常用的辦法是利用棧和隊列的特性去改造。

6.1將區間按照基準值劃分為左右兩半部分的常見方式

6.1.1Hoare版本

Hoare版本（以實現升序為例）的思想如下：

1.keyi為基準值的下標，定義數組a的兩個下標left和right，left位于區間的最左側，right位于區間的最右側

2.right先走，R往區間左側走，直到找到比a[keyi]小的值停下來，left后走，往區間右側走，直到找到比a[keyi]大的值停下來，然后交換a[left]和a[right]的值

3.重復進行2過程，直到left和right相遇，最后交換a[keyi]和a[left]的值

Hoare版本的單次快排原理圖如下：

使用Hoare版本的快排實現代碼如下：

// 快速排序hoare版本 int PartSort1(int* a, int left, int right) {int keyi = left;while (left < right){while (left < right && a[right] >= a[keyi]){right--;}while (left < right && a[left] <= a[keyi]){left++;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);return left; }void QuickSort1(int* a, int left, int right) {if (left >= right){return;}int keyi = PartSort1(a, left, right);// [left,keyi-1] keyi [keyi+1,right] QuickSort1(a, left, keyi-1);QuickSort1(a, keyi+1, right);}

6.1.2挖坑法

挖坑法（以實現升序為例）的思想如下：

1.定義數組a的兩個下標left和right，left位于區間的最左側，right位于區間的最右側

2.將數組的第一個數據存入一個臨時變量key中，key所在的下標成為一個坑位

3.right先走，right往區間左側走，找到比key值小的數，找到后，將該值放入坑位，同時該值的位置成為一個新坑位

4.left后走，left往區間右側走，找到比key值大的數，找到后，將該值放入坑位，同時該值的位置成為一個新坑位

5.重復進行3，4兩步，直到left和right相遇，然后將key的值放入坑位

挖坑法的單次快排原理圖如下：

使用挖坑法的快排實現代碼如下：

// 快速排序挖坑法 int PartSort2(int* a, int left, int right) {int key = a[left];int pit = left;while (left < right){//找小while (left < right && a[right] >= key){right--;}//把找到的小的值放到坑里a[pit] = a[right];//找到的小成為新坑pit = right;//找大while (left < right && a[left] <= key){left++;}//把找到的大的值放到坑里a[pit] = a[left];//找到的大成為新坑pit = left;}a[pit]=key;return left; } void QuickSort2(int* a, int left, int right) {if (left >= right){return;}int keyi = PartSort2(a, left, right);// [left,keyi-1] keyi [keyi+1,right] QuickSort1(a, left, keyi - 1);QuickSort1(a, keyi + 1, right); }

6.1.3前后指針法

前后指針法（以實現升序為例）的思想如下：

1.keyi為基準值的下標，定義數組a的兩個指針prev和cur，prev指向數組的開頭，cur指向數組開頭的后一個位置

2.判斷cur指針指向的數據是否小于key,若小于，則prev++，并且將cur指向的內容與prev指向的內容交換，然后cur指針++，若大于，則prev指針不動，cur++

3.重復進行2步驟，直到cur走到數組越界，此時交換a[keyi]和prev指向的內容

前后指針法的單次快排原理圖如下：

使用前后指針法的快排實現代碼如下：

// 快速排序前后指針法 int PartSort3(int* a, int left, int right) {int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){//low的方法/*if(cur<right&&a[cur] <= a[key]){prev++;Swap(&a[cur], &a[prev]);}cur++;*///大佬的寫法if (a[cur] < a[keyi] && a[++prev] != a[cur]){Swap(&a[prev], &a[cur]);}++cur;}Swap(&a[keyi], &a[prev]);return prev; }void QuickSort3(int* a, int left, int right) {if (left >= right){return;}int keyi = PartSort3(a, left, right);// [left,keyi-1] keyi [keyi+1,right] QuickSort1(a, left, keyi - 1);QuickSort1(a, keyi + 1, right); }

6.2快速排序的優化

6.2.1針對有序數組快排效率較低進行優化

我們先來做一組實驗，當數組有序時，使用我們剛剛寫的快速排序和冒泡排序對數組進行排序計算：

//冒泡排序與快速排序計算有序數組時的時間競速賽 void TestOP() {const int N = 10000;//計算10000長的數組int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);//將有序數據寫入數組for (int i = 0; i < N; ++i){a1[i] = i;a2[i] = a1[i];}//計時int begin1 = clock();BubbleSort(a1,N);int end1 = clock();int begin2 = clock();QuickSort3(a2, 0, N);int end2 = clock();//打印出他們的運行時間printf("BubbleSort:%d\n", end1 - begin1);printf("QuickSort:%d\n", end2 - begin2); }

實驗結果為：

?我們發現快排的運行時間居然比最垃圾的冒泡排序的運行時間都長！那你快排還怎么稱王！如果我們再次增大N，使得計算的數據位100000，會發生什么呢？

?什么！直接程序就崩了？我們來調試一下看看是哪里出了問題

?原來是棧爆了！在實際情況中，我們不免會碰到一組數據是有序或者接近有序，這個時候快排的效率就會變的很差，那么我們如何針對這種情況優化快速排序呢？答案當然是可以！為什么棧爆了，因為遞歸的層次太深了，那如何減少遞歸的次數呢？我們可以改變每次遞歸時的key值，防止這個key每次都是在區間的最左側或者最右側（數組有序就會出現這種情況），我們可以采用三數取中選key的方法，這個key不是數組中最大和最小的數據，那么數組遞歸的層次就會變少。改進算法程序如下：

//選中值 int GetMidIndex(int* a, int left, int right) {//int mid = (left + right) / 2;int mid = left + (right - left) / 2;// left mid rightif (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}} }int PartSort4(int* a, int left, int right) {int midi = GetMidIndex(a, left, right);Swap(&a[midi], &a[left]);int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){//大佬的寫法if (a[cur] < a[keyi] && a[++prev] != a[cur]){Swap(&a[prev], &a[cur]);}++cur;}Swap(&a[keyi], &a[prev]);return prev; }void QuickSort4(int* a, int left, int right) {if (left >= right){return;}int keyi = PartSort4(a, left, right);// [left,keyi-1] keyi [keyi+1,right] QuickSort1(a, left, keyi - 1);QuickSort1(a, keyi + 1, right); }

用10000個有序數組實驗一下：

?發現速度確實變快了，縮減到了原來的一半。

6.2.2小區間優化

前面說到，如何提升快排的效率，就是減少遞歸的次數，那么是否還有別的方法能繼續減少遞歸的次數呢？其實快排就是使用一次次遞歸將我們原來的大區間分為小區間，快排遞歸的展開圖可以看作一棵二叉樹。

?可以看到，越往小區間分，需要的遞歸層次就越多，那么當區間很小時，我們可以不再使用遞歸劃分的思路讓他有序，而是直接使用插入排序對小區間排序，減少遞歸調用。實現代碼如下：

void QuickSort4(int* a, int left, int right) {if (left >= right){return;}// 小區間直接插入排序控制有序if (right - left + 1 <= 30){InsertSort(a + left, right- left + 1);}else{int keyi = PartSort4(a, left, right);// [left,keyi-1] keyi [keyi+1,right] QuickSort1(a, left, keyi - 1);QuickSort1(a, keyi + 1, right);}}

測試一下10萬個有序數據改進后的運行速度：

?可見小區間優化是能夠提升快排的運行效率的！

為了避免篇幅過長，歸并排序我們就放到下期吧！

總結

以上是生活随笔為你收集整理的机械转码日记【5】《数据结构》常见排序算法及对比（第一次画动图）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。