---

前言

1.插入排序（直接插入排序 和 希爾排序）、選擇排序（直接選擇排序 和 堆排序）、交換排序（冒泡排序 和 快速排序）和歸并排序
2.重點內容：快速排序（三個版本的算法思路及代碼實現 以及 快速排序的復雜度討論及其優化方法：隨機選取基準值 、三數取中選取基準值 和 三路劃分）

---

一、排序概念及常見排序算法框圖

1.排序概念

所謂排序，就是使?串記錄，按照其中的某個或某些關鍵數據的大小，遞增或遞減的排列起來的操作。

2.常見排序算法框圖

非比較排序中暫只介紹計數排序

二、實現比較排序算法

1.插入排序

1.1 直接插入排序

直接插入排序是?種簡單的插入排序法，其基本思想是：把待排序的記錄按其關鍵碼值的大小逐個插入到?個已經排好序的有序序列中，直到所有的記錄插入完為止，得到?個新的有序序列 。

void direct_insert_sort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = arr[end + 1];while (end >= 0){if (tmp < arr[end]){arr[end + 1] = arr[end];end--;}elsebreak;}arr[end + 1] = tmp;}
}

直接插入排序的特性總結：

1. 元素集合越接近有序，直接插入排序算法的時間效率越高
2. 時間復雜度（按最壞情況）：O(N^2)
3. 空間復雜度：O(1)

1.2 希爾排序

希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數gap（通常 gap = n/2 或 n/3+1，n為數組元素個數），把待排序數據分成gap組，所有的距離相等的數據分在同?組內，并對每?組內的數據進行插入排序，然后 gap = n/2（或 n/3+1）得到下一個整數，再將數組分成gap組，對每?組內的數據排序，當gap=1時，就相當于直接插入排序。
直接插入排序算法的缺陷是它的時間復雜度在最優情況和最差情況下相差極大。希爾排序在直接插入排序算法的基礎上進行改進，通過幾輪分組排序（輪次越后面的排序，數組會越有序，效率會更高）使數組在最后一輪直接插入排序時接近有序，最后一輪直接插入排序效率會接近O(N)。
綜合來說，希爾排序的效率肯定是要高于直接插入排序算法的。

void shell_sort(int* arr, int n)
{int gap = n;while(gap>1){ gap = gap / 2;for (int i = 0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while (end >= 0){if (tmp < arr[end]){arr[end + gap] = arr[end];end -= gap;}elsebreak;}arr[end + gap] = tmp;}}
}

希爾排序的時間復雜度取決于增量序列的選擇（gap劃分方法的選擇），不同增量序列會導致不同的性能表現：

（1）原始希爾序列（$n/2,n/4,\dots ,1$）

• 最壞情況：$O(n^2)$（與直接插入排序相同）
• 平均情況：實際應用中約為 $O(n^{1.5})$，但缺乏嚴格證明。

（2）Hibbard 序列（$1,3,7,15,\dots ,2^k?1$）

• 最壞情況：$O(n^{3/2})$
• 平均情況：接近 $O(n^{5/4}))$。

（3）Sedgewick 序列（$1,5,19,41,\dots$）

• 最壞情況：$O(n^{4/3})$
• 平均情況：接近 $O(n{\log }^{2}n)$，是已知最優增量序列之一。

增量序列	最壞時間復雜度	平均時間復雜度	空間復雜度
原始序列	$O(n^2)$	$O(n^{1.5})$（經驗）	$O(1)$
Hibbard 序列	$O(n^{3/2})$	$O(n^{5/4})$	$O(1)$
Sedgewick 序列	$O(n^{4/3})$	$O(n{\log }^{2}n)$	$O(1)$

實際應用中，希爾排序通常比 $O(n^2)$ 的算法（如冒泡排序）快得多，但不如 $O(n\log n)$ 的算法（如快速排序、歸并排序）。

2.選擇排序

2.1 直接選擇排序

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

優化版本：每?次從待排序的數據元素中選出一組最小值和最大值，分別存放在序列的起始位置和末尾位置，一次可以確定兩個元素的位置，直到全部待排序的數據元素排完 。

void swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void direct_select_sort(int* arr, int n)
{int left = 0;int right = n - 1;while (left < right){int min = left;int max = left;int cur = left + 1;while (cur <= right){if (arr[cur] > arr[max])max = cur;if (arr[cur] < arr[min])min = cur;cur++;}swap(&arr[left], &arr[min]);if (left == max)max = min;swap(&arr[right], &arr[max]);left++;right--;}
}

時間復雜度計算：
第一次遍歷n個元素的數組，確認一組最大最小值；
第二次遍歷n-2個元素的數組，確認一組最大最小值；
……
最后一次遍歷2（或3）個元素的數組。
所以計算式子為：2+4+……+（n-2）+ n = n ^ 2 + n
最終得到時間復雜度為：O(N^2)

直接選擇排序的特性總結：

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

2.2 堆排序

堆是一棵完全二叉樹，使用順序結構的數組來存儲數據。堆中某個結點的值總是不大于（或不小于）其父結點的值，將根結點最大的堆叫做大堆或大根堆，根結點最小的堆叫做小堆或小根堆。

核心思想總結
利用堆的性質高效地找到最大值（或最小值）并逐步完成排序。 其核心在于：

1. 構建堆：將無序數組轉化為堆結構。
2. 反復提取極值：每次提取堆頂元素后調整堆，最終得到有序序列。

#include <queue>
#include <vector>
using namespace std;void heap_sort(int* arr, int n)
{priority_queue<int,vector<int>,greater<int>> hp; // priority_queue是C++的STL庫中自帶的堆結構，直接調用priority_queue生成一個小堆。// C語言要使用堆排序還需要自己先實現一個堆結構for (int i = 0; i < n; i++){hp.push(arr[i]); // 先把數組中所有元素插入小堆中（將無序數組轉化為堆結構）} int i = 0;while (!hp.empty()){arr[i++] = hp.top(); // 每次提取堆頂元素后調整堆，最終得到有序序列hp.pop();} 
}

堆排序的特性總結:

1. 時間復雜度： $O(n\log n)$
2. 空間復雜度： $O(1)$

3.交換排序

3.1 冒泡排序

冒泡排序的核心思想就是：兩兩相鄰的元素進行比較，滿足條件進行交換；一趟冒泡排序確定一個數的位置。

冒泡排序改良：
（1）設置一個變量，讓它可以判斷一趟冒泡排序中有無進行數組元素交換。
（2）當一趟冒泡排序中無任何一次數組元素交換，說明數組中元素已經有序，這時可提前結束循環。

void bubble_sort(int* arr, int n)
{for (int i = 0; i < n; i++){int exchange = 0; // 設置變量exchange，用來判斷一趟冒泡排序中有無進行數組元素交換for (int j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1]){exchange = 1;swap(&arr[j], &arr[j + 1]);}} if(exchange == 0){break;}}
}

時間復雜度計算（按最壞情況）：
每趟冒泡排序確定一個元素的位置，所以n個元素要進行n-1次冒泡排序。
第一趟冒泡排序要進行n-1次比較，確認一個元素的位置；
第二趟冒泡排序要進行n-2次比較（比上一趟少進行一次比較，因為確定了位置的元素無需再進行比較），再確認一個元素的位置；
……
依此類推，第n-1趟冒泡排序只需要進行1次比較
所以計算式子為：1+2+……+（n-2）+（n-1）=（n ^ 2）/ 2 - n/2
最終得到時間復雜度為：O(N^2)

冒泡排序的特性總結:

1. 時間復雜度： O(N^2)
2. 空間復雜度： O(1)

3.2 快速排序

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

3.2.1 hoare版本

算法思路 ：

1. 確定基準值（此處直接選擇最左元素為基準值），用key標記其下標；創建left和right標記，left起始指向key+1位置，right起始指向末尾位置
2. 從右向左找出比基準值小的數據，用下標right標記；從左向右找出比基準值大的數據，用下標left標記；然后right和left指向的數據互換，進入下次循環；期間一旦left>right，循環直接終止
3. 結束循環后，right所在的位置就是基準值的正確位置，把基準值交換到right位置
4. 以基準值位置劃分數組，左邊的數組<=基準值，右邊的數組>=基準值
5. 接著對左邊和右邊數組進行以上同樣的操作，不斷劃分數組，直到無法再進行劃分
   

void swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void hoare_quicksort(int* arr, int begin, int end)
{int key = begin;int left = begin + 1;int right = end;while (left <= right){while (left <= right && arr[right] >= arr[key])right--;while (left <= right && arr[left] <= arr[key])left++;if (left <= right){swap(&arr[left], &arr[right]);right--;left++;}}swap(&arr[key], &arr[right]);key = right; // [begin，key-1] key [key+1，end]if (begin < key - 1)hoare_quicksort(arr, begin, key - 1);if (key + 1 < end)hoare_quicksort(arr, key + 1, end);
}

3.2.2 挖坑法

算法思路 ：

1. 確定基準值（此處直接選擇最左元素為基準值），創建變量key保存基準值；創建left和right標記，left起始指向開頭位置（起始以left指向位置為"坑"位），right起始指向末尾位置
2. 首先移動right標記從右向左找出比基準值小的數據，找到后立即放入左邊"坑"位中，當前位置變為新的"坑"位，然后移動left從左向右找出比基準值大的數據，找到后立即放入右邊"坑"位中，當前位置變為新的"坑"，循環進行此過程，過程中一旦left和right相遇，循環立即終止。
3. 結束循環后，當前的"坑"位就是基準值的正確位置，將最開始用變量key存儲的基準值放入當前的"坑"位中
4. 以基準值位置劃分數組，左邊的數組<=基準值，右邊的數組>=基準值
5. 接著對左邊和右邊數組進行以上同樣的操作，不斷劃分數組，直到無法再進行劃分
   
   

void digholes_quicksort(int* arr, int begin, int end)
{int key = arr[begin];int left = begin;int right = end;while (left < right){while (left < right && arr[right] >= key)right--;if (left == right)break;elsearr[left] = arr[right];while (left < right && arr[left] <= key)left++;if (left == right)break;elsearr[right] = arr[left];}arr[right] = key; // [begin，right-1] right [right+1，end]if (begin < right - 1)digholes_quicksort(arr, begin, right - 1);if (right + 1 < end)digholes_quicksort(arr, right + 1, end);
}

3.2.3 lomuto前后指針

算法思路 ：

1. 確定基準值（此處直接選擇最左元素為基準值），用key標記其下標；創建prev和cur標記，prev起始指向開頭位置，cur起始指向prev+1位置
2. 首先移動cur標記從左向右找出比基準值小的數據，找到之后，prev先后移一位，然后將cur和prev指向的數據交換，緊接著cur后移一位，繼續循環進行此過程，直到cur越界，循環才終止。
3. 結束循環后，prev所在的位置就是基準值的正確位置，把基準值交換到prev位置
4. 以基準值位置劃分數組，左邊的數組<=基準值，右邊的數組>=基準值
5. 接著對左邊和右邊數組進行以上同樣的操作，不斷劃分數組，直到無法再進行劃分
   
   

void lomuto_quicksort(int* arr, int begin, int end)
{int key = begin;int prev = begin;int cur = prev + 1;while (cur <= end){while (cur <= end && arr[cur] >= arr[key])cur++;if (cur <= end){prev++;swap(&arr[cur], &arr[prev]);cur++;}}swap(&arr[key], &arr[prev]);key = prev; // [begin，key-1] key [key+1，end]if (begin < key - 1)lomuto_quicksort(arr, begin, key - 1);if (key + 1 < end)lomuto_quicksort(arr, key + 1, end);
}

3.3 快速排序的復雜度討論及其優化

3.3.1 快速排序的復雜度

時間復雜度分析：

1. 最好情況

   • 每次劃分都能將數組均勻分成兩部分（每次選的基準值都接近中位數）。
   • 遞歸深度為 $\log n$，每層需遍歷 $n$ 個元素（實際就第一層需遍歷n個元素，每層遞歸都會確定一些元素的位置，遞歸層數越深，需遍歷的元素越少，但統一按每層遍歷n個元素計算比較方便）。
   • 時間復雜度：$O(n\log n)$。

2. 平均情況

   • 假設基準值通過隨機選擇或三數取中法選出，劃分的均衡性服從概率分布。
   • 數學期望計算后仍為 $O(n\log n)$。
   • 時間復雜度：$O(n\log n)$。

3. 最壞情況

   • 每次劃分極不均衡（如數組已有序且固定選第一個元素為基準值）。
   • 遞歸深度為 $n$，總操作次數為 $n+(n?1)+?+1=\frac{n(n+1)}{2}$。
   • 時間復雜度：$O(n^2)$。

空間復雜度分析：

1. 最好情況

   • 遞歸深度為 $\log n$，棧空間占用與遞歸深度成正比。
   • 空間復雜度：$O(\log n)$。

2. 平均情況

   • 遞歸深度仍為 $\log n$（通過隨機化選擇基準值減少最壞概率）。
   • 空間復雜度：$O(\log n)$。

3. 最壞情況

   • 遞歸深度為 $n$（如每次僅處理一個元素）。
   • 空間復雜度：$O(n)$。

• 優化策略：隨機選擇或三數取中法選擇基準值，可有效降低與最壞情況1類似場景（數組有序或部分有序）的時間和空間復雜度 ；三路劃分法 可有效降低與最壞情況2類似場景（數組存在大量重復數據）的時間和空間復雜度。
• 空間占用：雖為原地排序，但需注意遞歸棧的隱式空間消耗。

3.3.2 隨機選取基準值 和 三數取中選取基準值

決定快排性能的關鍵點是每次單趟排序后，基準值對數組的分割，如果每次選的基準值都接近數組中的中位數，那么快排的遞歸樹就是顆均勻的滿二叉樹，性能最佳。但是實踐中雖然不可能每次都是二分居中，但是性能也還是可控的。但是如果出現每次選到最小值/最大值，劃分為0個和N-1的子問題時，時間復雜度為O(N^2)，數組有序并且每次固定選第一個元素為基準值前不進行任何干預，就會出現這樣的問題。
我們仍然可以采用第一個元素作為基準值的方法，不過在那之前進行隨機選取 或 三數取中法選出基準值，再把選出的基準值換到第一個元素，這樣可以有效減少因數組有序或部分有序而降低快排效率的情況。

1. 隨機選取基準值
   每次排序時，從當前數組中隨機選擇一個元素作為基準值，再通過交換操作將其移動到數組的起始位置，最后進行常規的劃分操作。

#include <time.h>
#include <stdlib.h>
void swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void random_select(int* arr, int begin, int end)
{srand((unsigned)time(NULL));// 隨機選擇基準值的位置，選擇區間在begin和end之間int key = rand() % (end - begin + 1) + begin;//把基準值位置的元素與begin位置元素互換，后續依然可以選第一個元素為基準值劃分函數  swap(&arr[key], &arr[begin]);
}

2. 三數取中選取基準值
   從當前子數組的首、中、尾三個位置取元素，選擇三者的中位數作為基準值，通過交換操作將其移動到數組的起始位置，最后進行常規的劃分操作。

void swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void median_select(int* arr, int begin, int end)
{int mid = begin + ((end - begin) >> 1);//計算數組中間的元素的下標  // 使用三數取中法選擇三者的中位數作為基準值并將其換到begin位置 if (arr[mid] < arr[end])//目標: arr[mid] >= arr[end]  {swap(&arr[mid], &arr[end]);}if (arr[begin] > arr[mid])//目標: arr[begin] <= arr[mid]  {swap(&arr[begin], &arr[mid]);}if (arr[begin] < arr[end]) //目標: arr[begin] >= arr[end]  {swap(&arr[begin], &arr[end]);}//此時，arr[mid] >= arr[begin] >= arr[end]  //begin位置上保存這三個位置中間的值，后續依然可以選第一個元素為基準值劃分函數  
}

3.3.3 三路劃分

快速排序的三路劃分是一種優化策略，用于處理數組中存在大量重復元素的情況。 它將數組劃分為三個區域：

• 小于基準值的部分（左段）
• 等于基準值的部分（中段）
• 大于基準值的部分（右段）

通過將重復元素集中到中間段，后續遞歸時只需處理左右兩段，避免對重復元素重復操作，從而提升效率。

算法思路（類似hoare的左右指針和lomuto的前后指針的結合） ：

1. 確定基準值（直接選擇最左元素為基準值），創建變量key保存基準值；創建 left、right 和 cur 標記，left起始指向開頭位置，right起始指向末尾位置，cur起始指向left+1位置
2. cur標記從左向右移動會遇到三種不同的情形，每種情形都會有對應的處理方式：

• 情形一：cur遇到比基準值小的值后跟left位置交換，換到左邊，left++，cur++；
• 情形二：cur遇到比基準值大的值后跟right位置交換，換到右邊，right–；
• 情形三：cur遇到跟基準值相等的值后，cur++。

3. 直到cur > right才結束以上過程
4. 以 left 和 right位置劃分數組，左邊的數組<基準值，右邊的數組>基準值
5. 接著對左邊和右邊數組進行以上同樣的操作，不斷劃分數組，直到無法再進行劃分
   

4.歸并排序

4.1 歸并排序的思想及實現

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

void merge_sort(int* arr, int begin, int end, int* tmp)
{int mid = begin + (end - begin) / 2;if (begin < mid)merge_sort(arr, begin, mid, tmp);if (mid + 1 < end)merge_sort(arr, mid + 1, end, tmp);int left1 = begin;int right1 = mid;int left2 = mid + 1;int right2 = end;int n = begin;while (left1 <= right1 && left2 <= right2){if (arr[left1] <= arr[left2])tmp[n++] = arr[left1++];elsetmp[n++] = arr[left2++];}while (left1 <= right1){tmp[n++] = arr[left1++];}while (left2 <= right2){tmp[n++] = arr[left2++];}while (begin <= end){arr[begin] = tmp[begin];begin++;}
}

三、比較排序算法總結

1.復雜度及穩定性分析

$$\begin{array}{lccccc}\text{算法}& \text{最好}& \text{最壞}& \text{平均時間復雜度}& \text{空間}& \text{穩定}\\ 冒泡排序& O(n)& O(n^2)& O(n^2)& O(1)& ?\\ 直接插入排序& O(n)& O(n^2)& O(n^2)& O(1)& ?\\ 歸并排序& O(n\log n)& O(n\log n)& O(n\log n)& O(n)& ?\\ 直接選擇排序& O(n^2)& O(n^2)& O(n^2)& O(1)& ?\\ 堆排序& O(n\log n)& O(n\log n)& O(n\log n)& O(1)& ?\\ 希爾排序& O(n\log n)& O(n^2)& O(n^{1.3})& O(1)& ?\\ 快速排序& O(n\log n)& O(n^2)& O(n\log n)& O(\log n)& ?\end{array}$$

2.測試代碼：比較排序性能對比

用以上各種比較排序算法排序同一組隨機生成的數據，測試時間（單位：毫秒）消耗，要在Release版本運行這段代碼（含遞歸的算法會在Debug版本生成更多調試數據，影響算法效率）:

#include "sort.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>void TestOP()
{srand(time(0));const int N = 50000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);int* tmp = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a1[i];} int begin1 = clock();direct_insert_sort(a1, N);int end1 = clock();int begin2 = clock();shell_sort(a2, N);int end2 = clock();int begin3 = clock();direct_select_sort(a3, N);int end3 = clock();int begin4 = clock();heap_sort(a4, N);int end4 = clock();int begin5 = clock();hoare_quicksort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();merge_sort(a6, 0, N - 1, tmp);int end6 = clock();int begin7 = clock();bubble_sort(a7, N);int end7 = clock();printf("direct_insert_sort:%d\n", end1 - begin1);printf("shell_sort:%d\n", end2 - begin2);printf("direct_select_sort:%d\n", end3 - begin3);printf("heap_sort:%d\n", end4 - begin4);printf("hoare_quicksort:%d\n", end5 - begin5);printf("merge_sort:%d\n", end6 - begin6);printf("bubble_sort:%d\n", end7 - begin7);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);free(tmp);
}int main()
{TestOP();return 0;
}

四、實現非比較排序算法

1.計數排序

計數排序是對哈希直接定址法的變形應用。 操作步驟：
1）統計相同元素出現次數
2）根據統計的結果將序列回收到原來的序列中

"找出最大值k，創建長度為k+1的計數數組"的方式有些時候會造成很大空間浪費，可以找出待排序數組中的最大最小值，按范圍開空間：

void count_sort(int* arr, int n)
{int min = arr[0], max = arr[0];for (int i = 1; i < n; i++){if (arr[i] > max)max = arr[i];if (arr[i] < min)min = arr[i];} int range = max - min + 1;int* count = (int*)calloc(range, sizeof(int));if (count == NULL){perror("calloc fail");return;}// 統計次數for (int i = 0; i < n; i++){count[arr[i] - min]++; } // 排序int j = 0;for (int i = 0; i < range; i++){while (count[i]--){arr[j++] = i + min;}}free(count);
}

---