💓博主個人主頁:不是笨小孩👀
?專欄分類:數據結構與算法👀 刷題專欄👀 C語言👀
🚚代碼倉庫:笨小孩的代碼庫👀
?社區：不是笨小孩👀
🌹歡迎大家三連關注，一起學習，一起進步！！💓

在這里插入圖片描述

排序算法

排序的概念
插入排序
希爾排序
選擇排序
冒泡排序
堆排序
快速排序
歸并排序
計數排序

排序的概念

排序：所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
穩定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的；否則稱為不穩定的。
內部排序：數據元素全部放在內存中的排序。
外部排序：數據元素太多不能同時放在內存中，根據排序過程的要求不能在內外存之間移動數據的排序。

常見的排序算法：

在這里插入圖片描述
除了這些排序以外，該有一個很奇怪的排序，計數排序，我們待會將，我們接下來，就從第一個排序開始：

插入排序

插入排序的思想很簡單就是把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列。插入排序可以理解為就是我們打撲克牌摸排的過程，摸一張排，依次比較然后將它插入的合適的位置。

我們看圖：
在這里插入圖片描述
這個排序很簡單，根據圖我們就可以把第一個數據當成有序的數據，然后后面的數據依次插入，直到將數據插入完，這樣就有序了。

代碼如下：

void InsertSort(int* arr, int n)
{for (int i = 0; i < n-1; i++){//end表示有序數據的最后一數的下標int end = i;//tmp保存需要插入的值int tmp = arr[end+1]; while (end >= 0){//依次比較如果比需要插入的數大，就往后移，否則就跳出循環if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}else{break;}}//跳出循環后將需要插入的數據放到end后面的位置arr[end + 1] = tmp;}
}

總結：

元素集合越接近有序，直接插入排序算法的時間效率越高
時間復雜度：O(N^2)
空間復雜度：O(1)，它是一種穩定的排序算法
穩定性：穩定

希爾排序

希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數gap，把待排序文件中所有記錄分成gap個組，所有距離為gap的記錄分在同一組內，并對每一組內的記錄進行排序。然后，重復上述分組和排序的工作。當到達=1時，所有記錄在統一組內排好序。

插入排序第一步我們需要預排序
預排序后插入排序就很快了，直接使用插入排序就可以了。但是當我們的gap=1是，希爾排序就相當于插入排序了。這里gap可以取很多值，但是要保證最后一次gap=1.

在這里插入圖片描述

代碼如下：

void ShellSort(int* arr, int n)
{int gap = n;//要進行多趟排序while (gap > 1){//+1是為了保證gap最后一次等于1gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){//每次分別排gap組數據，每組間隔gap個數據，一共gap組int end = i;int tmp = arr[i + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}

總結：

希爾排序是對直接插入排序的優化。
當gap > 1時都是預排序，目的是讓數組更接近于有序。當gap == 1時，數組已經接近有序的了，這樣就會很快。這樣整體而言，可以達到優化的效果。我們實現后可以進行性能測試的對比。
希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，因此在好些樹中給出的希爾排序的時間復雜度都不固定：我們記住大約就等于O(N^1.3)
穩定性：不穩定

選擇排序

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

在這里插入圖片描述

我們這里實現的是依次找大的，然后放到最后面，和圖不太一樣，但是思想都一樣。

代碼如下：

void SelectSort(int* arr, int n)
{int end = n - 1;while (end>0){//每次初始化最大在0處，防止maxi到已經在排好序的位置int maxi = 0;for (int i = 0; i <= end; i++){if (arr[i] > arr[maxi]){maxi = i;}}//找到后和最后一個數據交換Swap(&arr[maxi], &arr[end]);end--;}
}

選擇排序我們這里可以優化一下，就是每次選出最小的和最大的，然后最小的放到左邊，最大的放到右邊，然后接著找剩余數據的最大最小，直到結束。

代碼如下：

void SelectSort(int* arr, int n)
{int begin = 0;int end = n - 1;while (begin < end){int maxi = begin;int mini = begin;//依次找大和找小for (int i = begin; i <= end; i++){if (arr[mini] > arr[i]){mini = i;}if (arr[maxi] < arr[i]){maxi = i;}}//找到后將大的數據放到后面Swap(&arr[maxi], &arr[end]);//防止最小的數據在最后面被換走了，及時修正if (mini == end){mini = maxi;}Swap(&arr[mini], &arr[begin]);begin++;end--;}
}

總結：

直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用
時間復雜度：O(N^2)
空間復雜度：O(1)
穩定性：不穩定

冒泡排序

冒泡排序大多數人應該都知道，它的基本思想就是依次比較，將大的數據冒到最后然后重復前面的過程，就可以完成排序。

在這里插入圖片描述
代碼如下：

void BubbleSort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){int flag = 1;for (int j = 1; j < n - i; j++){if (arr[j] < arr[j - 1]){Swap(arr + j, arr + j - 1);flag = 0;}}if (flag == 1){break;}}
}

總結：

冒泡排序是一種非常容易理解的排序
時間復雜度：O(N^2)
空間復雜度：O(1)
穩定性：穩定

堆排序

堆排序前面已經講過一次了，這里就不做過多的解釋了，想要詳細了解請戳。
這里是引用

總結：

堆排序使用堆來選數，效率就高了很多。
時間復雜度：O(N*logN)
空間復雜度：O(1)
穩定性：不穩定

快速排序

快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素序列中
的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右
子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。

我們每次可以將數組劃分為兩部分，keyi是那個選出來的數的最終的下標，然后第一次排序后就是[left,keyi-1],keyi,[keyi+1,right]，我們每一趟要保證的是keyi左邊的數據逗比key小，右邊的都比它大，然后左區間重復這個操作，右區間也重復這個操作，這就有點像二叉樹的前序遍歷，直到每個區間只剩下一個值，或者區間不存在時，我們結束遞歸。

快排的整體框架：

void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}int keyi = partSort(arr,left,right);QuickSort(arr,left, keyi - 1);QuickSort(arr,keyi + 1, right);}

這里的partSort就是我們的單趟排序，我們講三種方法：

hoare版本

我們需要兩個指針，一個從左邊開始走，一個從右邊開始走，再定義一個key，和keyi，keyi保存key的小標，如果左邊左key就右邊先走，右邊左key就左邊先走，，然后左邊找比key大的數，右邊找比key小的數，找到后交換，然后接著走，直到相遇，然后把相遇的位置和key交換一下。

為什么左邊做key右邊先走呢？

因為這樣可以保證相遇的位置一定是比key小等于的數，相遇無非就是兩種情況，L遇到R，R遇到L，如果是L遇到R，我們讓右邊先走，R停下的位置一定是比key小的數，如果是R遇L，假設數組中的數都比key大，所以key遇到L是就是等于key，所以我們左邊做key讓右邊先走，是可以保證相遇位置一定比key小的。

代碼如下：

int partSort1(int* arr, int left, int right)
{int keyi = left;while (left < right){//右邊找小while (left < right && arr[right] >= arr[keyi]){right--;}//左邊找大while (left < right && arr[left] <= arr[keyi]){left++;}Swap(&arr[left], &arr[right]);}Swap(&arr[left], &arr[keyi]);return left;
}

挖坑法

我們還是將左邊做key，然后保存它的值，然后它就是一個坑，還是兩個指針，由于左邊有一個坑，所以右邊就要找小的數來填這個坑，然后將右邊的那個位置變成新的坑，然后左邊找大，找到后接著填坑，更新坑的位置，L和R一定有一個是坑，所以，當他們相遇時，那個位置一定是坑，然后將key放進去即可。

代碼如下：

int partSort2(int* arr, int left, int right)
{int hole = arr[left];int keyi = left;while (left < right){while (left < right && arr[right] >= hole){right--;}arr[keyi] = arr[right];keyi = right;while (left < right && arr[left] <= hole){left++;}arr[keyi] = arr[left];keyi = left;}arr[keyi] = hole;return keyi;
}

前后指針法

定義兩個指針一個prev一個cur，cur用來遍歷數組，還是用左邊的值來做key，然后將cur找到比key小的值就和++prev位置的數交換直到遍歷結束，然后再把prev位置的值可key交換即可。

代碼如下：

int partSort3(int* arr, int left, int right)
{int keyi = left;int cur = left + 1;int prev = left;while (cur <= right){if (arr[cur] < arr[keyi]&&++prev!=cur){Swap(&arr[prev], &arr[cur]);}cur++;}Swap(&arr[prev], &arr[keyi]);return prev;
}

快速排序的非遞歸版本

非遞歸的話，我們用隊列和棧都是可以的，但是想要模仿遞歸的路徑的話我們就要使用棧，我們先把數組的整個區間放到棧里面，然后在進行一趟排序后，我們把排出來的左區間和右區間入棧，由于先走左邊，所以就要先把右邊的區間壓棧，然后依次進行，只要區間存在，我們就壓，只要棧不為空，就代表一直有區間未處理。所以我們就一直重復操作，當然單趟排序的話，用上面的那種方法都可以。

代碼如下：

void QuickSortNonR(int* arr, int left, int right)
{Stack st;StackInit(&st);StackPush(&st,right);StackPush(&st, left);while (!StackEmpty(&st)){int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);int keyi = partSort1(arr, begin, end);if (keyi + 1 < end){StackPush(&st, end);StackPush(&st, keyi + 1);}if (keyi - 1 > begin){StackPush(&st, keyi - 1);StackPush(&st, begin);}}
}

快速排序，還可以優化，他的效率和選的key的關系很大，所以我們有種方法叫做三數取中，左邊的值、右邊的值、中間的值，然都找到這三個數中間的數，把他換到左邊，就可以了。

總結：

快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
時間復雜度：O(N*logN)
空間復雜度：O(logN)
穩定性：不穩定

歸并排序

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

歸并排序需要將區間分為兩部分，然后兩部分都要有序才能歸并，那左右區間又可以分割，以此類推，當區間只有一個數的時候就可以認為有序，這時我們可以走一個類似與二叉樹后序遍歷的思路，我們想歸并左右區間，但是左右區間都無序，我們就遞歸左邊讓左邊有序，在遞歸右邊讓右邊有序，最后再左右歸并，就可以排好了。

在這里插入圖片描述

我們這里就需要一個數組來保存我們歸并的值，我們取兩段區間的值依次比較，拿小的尾插到tmp數組中，等歸并完再拷回原數組，即可。

代碼如下：

void _MergeSort(int* arr, int left, int right,int* tmp)
{if (left >= right){return;}//分割區間int mid = (left + right) / 2;_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid+1, right, tmp);int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int k = left;while (begin1 <= end1 && begin2 <= end2){//選小的來尾插if (arr[begin1] <= arr[begin2]){tmp[k++] = arr[begin1++];}else{tmp[k++] = arr[begin2++];}}//不管哪個沒有拷貝完，因為區間是有序地，直接尾插就可以while (begin1 <= end1){tmp[k++] = arr[begin1++];}while (begin2 <= end2){tmp[k++] = arr[begin2++];}//拷貝回原數組memcpy(arr + left, tmp + left, (right - left + 1) * sizeof(int));}
void MergeSort(int* arr, int left, int right)
{int* tmp = (int*)malloc(sizeof(int) * (right - left + 1));//不能在這個函數中遞歸，不然每次都要開辟數組_MergeSort(arr, left, right,  tmp);free(tmp);
}

歸并排序的非遞歸版本

我們會發現歸并排序用隊列和棧都用不了，但是我們可以使用循環來解決它，首先我們需要一個gap來記錄每組歸并的數據有幾個，然后控制區間，來進行歸并。
但是在歸并中，會存在很多的越界問題，比如end1越界了，或者begin1越界了，但是這兩種情況我們都很好處理，等處理到這種錯誤時我們可以看成只剩下一組數據，就可以不用動，放在原數就好，等待下一輪歸，直接break跳出就可以，還有一種情況是end2越界了，這時還有一部分數據需要歸并，那我們就調整end2為n-1就可以了。

在這里插入圖片描述

代碼如下：

void MergeSortNonR(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);int gap = 1;//gap表示每組數據的長度while (gap < n){for (int i = 0; i < n; i += 2 * gap){//控制區間int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;int k = i;//越界即使調整或退出if (end1 >= n || begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] <= arr[begin2]){tmp[k++] = arr[begin1++];}else{tmp[k++] = arr[begin2++];}}while (begin1 <= end1){tmp[k++] = arr[begin1++];}while (begin2 <= end2){tmp[k++] = arr[begin2++];}//每次歸并完拷貝會原數組memcpy(arr+i, tmp+i, sizeof(int)*(end2-i+1));}gap *= 2;}free(tmp);
}

總結：

歸并的缺點在于需要O(N)的空間復雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
時間復雜度：O(N*logN)
空間復雜度：O(N)
穩定性：穩定

計數排序

計數排序是非常奇怪的排序，它不需要比較任何數據，他開辟一個和最大值一樣的數組，然后將該數組初始化為0，然后原遍歷數組，將原數組的值對應到我們開辟數組的下標，出現一次我們就++該位置，然后統計每個位置出現的次數，然后在依次拷貝回原數組，就可以了。
但是如果數據很大很集中，我們就沒必要開那么大，會很浪費，我們需要找到最大值和最小值，然后使用相對位置，就可以了，每個數對應到減去最小值的那個小下標，這樣我們數組也不用開的很大。

代碼如下：

void CountSort(int* arr, int n)
{int min = arr[0];int max = arr[0];//找最大值和最小值for (int i = 0; i < n; i++){if (max < arr[i]){max = arr[i];}if (min > arr[i]){min = arr[i];}}//計算區間方便開數組int c =max-min+1;int* nums = (int*)malloc(sizeof(int) * c);memset(nums, 0, c * sizeof(int));//統計for (int i = 0; i < n; i++){nums[arr[i]-min]++;}int k = 0;//拷貝回原數組for (int i = 0; i < c; i++){while (nums[i]--){arr[k++] = i+min;}}free(nums);
}