數據結構：八大排序(冒泡，堆，插入，選擇，希爾，快排，歸并，計數)詳解

一.冒泡排序

二.堆排序

三.插入排序

四.選擇排序

五.希爾排序

六.快速排序

1.Lomuto版本（前后指針法）

2.Lomuto版本的非遞歸算法

3.hoare版本（左右指針法）

4.挖坑法找分界值：

七.歸并排序

八.計數排序

九.排序算法復雜度及穩定性分析

一.冒泡排序

冒泡排序即qsort排序，其在幾大排序中屬于那種效率較低的排序方式，相同條件下，qsort排序的時間要比其他排序多幾十乃至幾千倍，但由于其在排序過程中不會輕易改變原來數據的相對位置，因此它也算是一種較為穩定的函數（關于排序函數的穩定性我會在下文帶著慢慢說明），以下是冒泡排序的具體原理與代碼：

在升序條件下，不斷遍歷左邊的數據以找其中最大者然后不斷循環放在右邊
//冒泡排序
void BubbleSort(int* arr, int n)
{int end = n;while (end){int flag = 0;for (int i = 1; i < end; ++i)//代表每一次進入循環左邊數據都會少一個{if (arr[i - 1] > arr[i]){int tem = arr[i];arr[i] = arr[i - 1];arr[i - 1] = tem;//右邊比左邊大就交換flag = 1;}}if (flag == 0){break;}--end;}
}
看懂這樣的代碼之后可以仔細想想：冒泡排序在最差的情況下（即恰好每一輪的找最大值都需要它一個不漏地遍歷其當時的所有數據）那么冒泡排序的時間復雜度為O（n^2）(即1一直累加到n-1)，最好的情況下就是O（n），同時，在冒泡排序的每一趟過程中，假設有兩個連續的一樣的數據，那么冒泡排序在遍歷過程中，是不會改變這兩個數據的相對位置的，因此在不考慮時間復雜度的情況下，所以我稱冒泡排序這種排序方式是一種穩定的排序方式

二.堆排序

堆排序的具體使用我在以下文章https://blog.csdn.net/2403_87691282/article/details/145888014?spm=1001.2014.3001.5501里有過說明，所以這里就允許我稍微偷下懶展示一下現成代碼吧：
//向下調整算法
void AdjustDown(HP* hp, int parent, int n)//n是向下調整的下界范圍
{int child = parent * 2 + 1;//公式while (child < n){//建小根堆if (child + 1 < n && hp->arr[child + 1] < hp->arr[child])//child+1的目的是確保兩個孩子結點都是有意義的結點{child++;}if (hp->arr[parent] > hp->arr[child]){swap(&hp->arr[parent], &hp->arr[child]);parent = child;child = parent * 2 + 1;}else{//我最小的孩子都比父節點大，那么這個堆就是正常堆了，直接退出break;}}
}// 升序，建?堆
// 降序，建?堆
// O(N*logN)//基于數組的堆排序
void HeapSort(int* a, int n)
{// a數組直接建堆 O(N)for (int i = (n-1-1)/2; i >= 0; --i){AdjustDown(a, n, i);}// O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}
堆排序的時間復雜度也是比較好理解的：n*log（n），log（n）是向下調整算法每一層遍歷需要的時間，n則是每一次為了出堆頂數據而進行的循環調用，由于每一次的出堆頂數據都需要調用一次向下調整算法，因此堆排序的時間復雜度為n*log（n），而且需要補充的一點是由于每一次的取堆頂出堆頂，可能會導致原待排序數據中相同數據的相對位置在堆排序后出現改變，因此也可以說盡管堆排序的效率在排序里算不錯的，但其穩定性是屬于不穩定的那一批

三.插入排序

插入排序的邏輯其實也不難：

1.從第一個元素開始，假設該元素已經被排序
2.取下一個元素tem，從已排序的元素序列從后往前遍歷
3.如果該元素大于tem，則將該元素移到下一位
4.重復步驟3，直到找到已排序元素中小于等于tem的元素
5.tem插入到該元素的后面，若已排序所有元素都大于tem，則將tem插入到下標為0的位置
6.循環步驟2~5
void InsertSort(int* arr, int n)
{for (int i = 0; i < n - 1; ++i){//記錄有序序列最后一個元素的下標int end = i;//待插入的元素int tem = arr[end + 1];//單趟排while (end >= 0){//比插入的數大就向后移if (tem < arr[end]){arr[end + 1] = arr[end];end--;}//比插入的數小，跳出循環else{break;}}//tem放到比插入的數小的數的后面arr[end  + 1] = tem;//代碼執行到此位置有兩種情況://1.待插入元素找到應插入位置（break跳出循環到此）//2.待插入元素比當前有序序列中的所有元素都小（while循環結束后到此）}
}
代碼補充解釋：由于end作為記錄有序數據的最后一個數據的變量，所以在大循環for中，end的實際值是一直在改變的，因此就需要在單趟排之后隨時重置tmp的位置，而且tmp作為始終處于end后一位的變量（作為end的偵察兵，始終為了確定end是否需要與后一位交換位置而存在），在小循環while里end值每交換一次，就代表其與tmp值交換位置，因此需要在每個小循環的最后再將end值--使其回到正確的實際值，同樣還有一點需要注意的就是直接插入排序的時間復雜度為O（n^2）,且由于其在遍歷過程中不會改變相同數據的相對位置，所以其排序性質是穩定的

四.選擇排序

選擇排序的思路也不算難，主要就是通過每次從待排序序列中挑一個最大再挑一個最小然后分別放在數組的兩端，依次類推：

具體代碼：
//選擇排序
void swap(int* a, int* b)
{int tem = *a;*a = *b;*b = tem;
}
void SelectSort(int* arr, int n)
{//保存參與單趟排序的第一個數和最后一個數的下標int begin = 0, end = n - 1;while (begin < end){//保存最大值的下標int maxi = begin;//保存最小值的下標int mini = begin;//找出最大值和最小值的下標for (int i = begin; i <= end; ++i){if (arr[i] < arr[mini]){mini = i;}if (arr[i] > arr[maxi]){maxi = i;}}//最小值放在序列開頭swap(&arr[mini], &arr[begin]);//最大值放在序列結尾swap(&arr[maxi], &arr[end]);++begin;--end;}
}
當理解了選擇排序后有一點需要注意的就是直接選擇排序的時間復雜度無論是最佳情況（即待排序數據已經排序完畢）還是最差情況（每一次找最大最小都要遍歷全部待排序數據）都是O（n^2）,這點與冒泡排序不同，冒泡排序雖然最差情況時與直接排序相同，但在最好情況下的時間復雜度卻是O（n），主要還是因為冒泡排序如果排已經拍好的數組時，其中的小循環幾乎已經不需要進入執行了，但直接選擇排序即便是遍歷已經排好的數組也仍舊需要從頭到尾遍歷一遍，并且直接選擇在遇到相同數據時同樣是有可能會改變原始數據的相對順序的，是不穩定的

五.希爾排序

希爾排序的邏輯可能就有些復雜：其基本思想為先選定?個整數（通常是gap=n/3+1），把待排序?件所有記錄分成各組，所有的距離相等的記錄分在同?組內，并對每?組內的記錄進行排序，然后gap=gap/3+1得到下?個整數，再將數組分成各組，進行插入排序，當gap=1時，就相當于直接插入排序，

再簡單點來說就是先將待排序列進行預排序，使待排序列接近有序，然后再對該序列進行一次插入排序，此時插入排序的時間復雜度為O(N)

由于它是在直接插入排序算法的基礎上進行改進?來的，綜合來說它的效率肯定是更高的
//希爾排序
void ShellSort(int* arr, int n)
{int gap = n;while (gap>1){//每次對gap折半操作gap = gap / 2;//單趟排序for (int i = 0; i < n - gap; ++i){int end = i;int tem = arr[end + gap];while (end >= 0){if (tem < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tem;}}
}
代碼方面的解釋也不算很難，希爾排序通過對原始數據不斷的分小組細化，然后對每一個小組使用直接插入排序，從而減少直接插入排序算法里循環的次數，希爾算法里對于其中小循環的解釋跟直接插入排序算法是有一樣的，都是基于end與tmp的相對位置不變，然后小的往前放，大的往后放并且隨時重置tmp（希爾里就是end+gap）使其一直處于end的前面而實現的算法，同樣，我們再說到其時間復雜度，這里希爾算法的時間復雜度由于數學理論的局限，因此：

但唯一可以確定的是，希爾排序確實在很大程度上優化了直接插入算法

六.快速排序

快速排序我認為是幾大排序里最復雜也是探究的最深的一個排序算法思想，其根本的邏輯就是通過先在原始數據任意建立一個參考點，然后通過各種方法使參考點的左邊的數據小于參考點，然后使參考點右邊的數據大于參考點

1.Lomuto版本（前后指針法）

思路：
1.選出一個keyi，一般是最左邊或是最右邊的。
2.起始時，prev指針指向序列開頭，cur指針指向prev+1。
3.若cur指向的內容小于keyi，則prev先向后移動一位，然后交換prev和cur指針指向的內容，然后cur指針++；若cur指向的內容大于key，則cur指針直接++，（因此在排序過程中在沒遇到大于keyi參考值時，prev和cur都會在下一步之前重合，只有當遇到大于參考值時，cur才會多走一步從而拉開與prev的距離，而這樣拉開一步的解雇就是使prev的下一步指向值是一個比參考值大的數，因此此時交換prev和cur就可以實現數據大的往后移動）如此進行下去，直到cur到達end+1(出界)位置，此時將keyi和prev指針指向的內容交換即可。

經過一次單趟排序，最終也能使得key左邊的數據全部都小于key，key右邊的數據全部都大于key。

4.然后也還是將key的左序列和右序列再次進行這種單趟排序，如此反復操作下去，直到左右序列只有一個數據，或是左右序列不存在時，便停止操作
//Lomuto前后指針
int _QuickSort2(int* arr, int left, int right)
{int keyi = left;int prev = left, cur = prev + 1;while(cur <= right){if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[prev], &arr[cur]);}++cur;}Swap(&arr[prev], &arr[keyi]);return prev;
}

2.Lomuto版本的非遞歸算法

非遞歸版本的快速排序就是在Lomuto算法的基礎上充分利用了棧的性質（這里有些具體的棧的操作我在之前有篇文章提過，具體請參考：https://blog.csdn.net/2403_87691282/article/details/145228592?spm=1001.2014.3001.5501），通過將數組的首尾元素存儲在棧里從而實現一種類似于不斷循環的二分數組的結構，而其中二分的核心即是我們最核心的代碼：Lomuto算法（找參考值）
#include<stdio.h>//定義棧的結構
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;      //指向棧頂的位置int capacity;//棧的容量
}ST;void QuickSortNonR(int* arr, int left, int right)
{ST st;STInit(&st);StackPussh(&st, right);StackPussh(&st, left);while (!StackEmpty(&st)){//取棧頂兩次int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);//[begin,end]--找基準值int key1 = begin;int prev = begin, cur = prev + 1;//Lomuto前后指針法排序while (cur <= end){if (arr[cur] < arr[key1] && ++prev != cur){Swap(&arr[prev], &arr[cur]);}cur++;}Swap(&arr[prev], &arr[key1]);key1 = prev;//重新設定基準值以區分兩個數組//begin key1 end//左序列【begin，key1-1】  右序列【key1+1，end】//要確保有效if (key1 + 1 < end){StackPush(&st, end);StackPush(&st, key1+1);}if (begin < key1-1){StackPush(&st, key1 - 1);StackPush(&st, begin);}}//銷毀棧STDestroy(&st);
}

3.hoare版本（左右指針法）

//快速排序   hoare版本(左右指針法)
void QuickSort(int* arr, int begin, int end)
{//只有一個數或區間不存在if (begin >= end)return;int left = begin;int right = end;//選左邊為keyint keyi = begin;while (begin < end){//右邊選小   等號防止和key值相等    防止順序begin和end越界while (arr[end] >= arr[keyi] && begin < end){--end;}//左邊選大while (arr[begin] <= arr[keyi] && begin < end){++begin;}//小的換到右邊，大的換到左邊swap(&arr[begin], &arr[end]);}swap(&arr[keyi], &arr[end]);keyi = end;//[left,keyi-1]keyi[keyi+1,right]QuickSort(arr, left, keyi - 1);QuickSort(arr,keyi + 1,right);
}
在這個算法里有兩點需要額外關注，一就是遞歸時所使用的函數的參數，這個就是三路遞歸法，之所以使用這樣的方法是因為在快排的雙指針法中，可以確保遞歸的平衡，避免Lomuto雙指針法里產生的元素集中在左側或者右側而產生的遞歸不平衡，二就是代碼過程中判斷指針是否運動時的等號，之所以在相等時也讓指針持續運動，是為了使數據中相同的元素最后集中在三路里的中間一路，以避免多次重復的遞歸計算

4.挖坑法找分界值：

思路：

? ? ? ? 創建左右指針，?先從右向左找出?基準?的數據，找到后?即放?左邊坑中，當前位置變為新的"坑"，然后從左向右找出?基準?的數據，找到后?即放?右邊坑中，當前位置變為新的"坑"，結束循環后將最開始存儲的分界值放?當前的"坑"中，返回當前"坑"下標（即分界值下標）
int _QuickSort(int* a, int left, int right)
{int mid = a[left];int hole = left;int key = a[hole];while (left < right){while (left < right && a[right] >= key){--right;}a[hole] = a[right];hole = right;while (left < right && a[left] <= key){++left;}a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}

七.歸并排序

總結來說：歸并排序是一種基于分治法的高效排序算法，其核心思想是將數組逐步拆分為更小的子數組進行排序，再將有序的子數組合并為整體有序的數組

void _MergeSort(int* a, int left, int right, int* tmp)
{if (left >= right){return;}int mid = (right + left) / 2;//[left,mid] [mid+1,right]_MergeSort(a, left, mid, tmp);_MergeSort(a, mid + 1, right, tmp);int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int index = begin1;//合并兩個有序數組為?個數組 while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index++] = a[begin1++];}else{tmp[index++] = a[begin2++];}}while (begin1 <= end1){tmp[index++] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}for (int i = left; i <= right; i++){a[i] = tmp[i];}
}void MergeSort(int* arr, int n)
{//外部申請臨時數組空間，因此不計入空間復雜度int* tmp = (int*)malloc(sizeof(int*)*n);_MergeSort(arr, 0, n - 1, tmp);free(tmp);
}

八.計數排序


void CountSort(int* a, int n)
{int min = a[0], max = a[0];for (int i = 1; i < n; i++){if (a[i] > max)max = a[i];if (a[i] < min)min = a[i];}int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);if (count == NULL){perror("malloc fail");return;}memset(count, 0, sizeof(int) * range);//初始化// 統計次數 for (int i = 0; i < n; i++){count[a[i] - min]++; }// 排序 int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}
}