歡迎來到我的Blog，點擊關注哦💕

前言

排序是一種基本的數據處理操作，它涉及將一系列項目重新排列，以便按照指定的標準（通常是數值大小）進行排序。在C語言中，排序算法是用來對元素進行排序的一系列步驟。

排序的概況

C語言中的排序算法是一系列用于將一組數據按照特定順序進行排列的算法。這些算法通常根據元素之間的大小關系來確定它們在最終排序結果中的位置。

衡量排序的標準

• 時間復雜度（參考：時間空間復雜度介紹）
• 輔助空間：有些排序算法在排序過程中需要額外的空間來輔助排序，例如歸并排序和快速排序。這些算法的輔助空間通常為O(n)，而有些算法如插入排序和冒泡排序的輔助空間為O(1)
• 穩定性：穩定性是指在排序過程中，相等鍵值的元素在原始序列中的相對位置是否保持不變。穩定排序算法會維持相等元素的相對次序，而不穩定排序算法則可能改變這些元素的相對次序。
• 特殊情況下性能：某些排序算法在特定情況下可能表現得更優，例如當數據已經部分有序時，插入排序和冒泡排序可能會更快。而快速排序在這種情況下可能會變慢。

冒泡排序（Bubble Sort）

冒泡排序概念

冒泡排序是一種交換排序，它的基本思想是：兩兩比較相鄰記錄的關鍵字，如果反序則交換，直到沒有反序的記錄為止。這個過程會重復進行，直到沒有再需要交換的元素，這意味著數列已經排序完成。這個過程就像是氣泡一樣，較小（或較大）的元素會逐漸“冒泡”到列表的頂端

代碼實現

冒泡排序算法的實現通常涉及兩個嵌套的for循環。外層循環控制每一輪的比較次數，內層循環用于比較相鄰元素并進行交換。

//冒泡排序
void BubbleSort(int* a, int n)
{for (int i = 0; i < n; i++){for (int j = i; j < n-i-1; j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);}}}
}

優化冒泡排序

當冒泡排序遇見 {2，1，4，5，6，7，8，9，10} 這樣的數據就會大大折扣性能。如遇見如此的數據進行排序，我們可以定義一個bool類型flag = false 當數據進行交換的時候我們改變flag；

代碼如下：

//冒泡排序
void BubbleSort(int* a, int n)
{for (int i = 0; i < n; i++){bool flag = false;for (int j = i; j < n-i-1; j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);flag = true;}if (flaf == false){break;}}}
}

冒泡排序復雜度分析

冒泡排序算法的時間復雜度為O(n^2）， 這是因為在最壞的情況下，即數組完全逆序時，冒泡排序需要進行n-1輪比較和交換，其中n是數組的長度。每一輪比較需要比較n-i次（i為當前輪數），因此總的比較次數為n*(n-1)/2。所以，冒泡排序的時間復雜度為O(n^2)

選擇排序（Selection Sort）

選擇排序的概念

選擇排序（Selection Sort）是一種簡單直觀的排序算法，它的基本思想是在每一輪中從不排序的子序列中選取最小（或最大）的元素，將其與子序列的起始位置的元素交換，從而逐漸構建起有序序列。

代碼實現

選擇排序思想簡單，排序大->小（小->大），就遍歷數組記錄即可。

//交換
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//選擇排序
void SelectSort(int* a, int n)
{int min = 0;int begin = 0;while (begin < n - 1){for (int i = begin; i < n; i++){if (a[i] < a[min]){min = i;}}Swap(&a[min], &a[begin]);++begin;}
}

優化選擇排序

選擇排序可以通過一些優化手段進行提升，例如使用哨兵變量來減少內層循環的判斷次數等。這些優化手段可以在一定程度上提高選擇排序的執行效率。（在這里就不實現了）

選擇排序的復雜度分析

選擇排序的時間復雜度為 O(n^2)，其中n是數組的長度。這是因為算法需要進行兩層循環，外層循環控制排序的輪數，內層循環則負責在每一輪中找到最小元素。

插入排序（Insertion Sort）

插入排序的概念

插入排序是一種簡單直觀的排序算法，它的基本思想是將未排序的元素插入到已排序元素形成的有序序列中。在每一輪排序中，都會將一個待排序的元素插入到它應該所在的位置，直到所有元素都被插入完畢。

代碼實現

定義循環進行比較將大（小）的值相后面依次挪動，直至尋找到比自己小（大）的值位置進行插入。

//插入排序
void InsertionSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}

插入排序的優化

• 可以進行二分插入，它通過二分查找來確定待插入位置，從而減少了比較和移動的次數。
• 希爾排序是對直接插入排序的優化，它通過增加一個間隙因子來分組排序，使得每個組內部的元素可以先進行排序，然后逐漸減小間隙因子，直到間隙因子為1，此時整個數組已經接近有序，插入排序的效率會得到提高

插入排序復雜度分析

• 最佳情況：如果輸入數組已經是完全有序的，插入排序只需要進行 n 次比較（每次比較后插入一個元素到已排序部分），而不需要進行任何交換。在這種情況下，時間復雜度是 O(n)。
• 平均情況：在平均情況下，插入排序的時間復雜度是 O(n^2)。這是因為每個元素都需要與已排序部分的多個元素進行比較，平均下來，每個元素需要比較 n/2 次。
• 最壞情況：如果輸入數組是完全逆序的，插入排序需要進行 n(n-1)/2 次比較和 n(n-1)/2 次交換，時間復雜度是 O(n^2)

希爾排序（Shell Sort）

希爾排序的概念

希爾排序（Shell Sort）是一種基于插入排序的算法，它通過引入增量序列，采取分組排序策略：將大數組分為若干個子序列，對每個子序列進行插入排序。隨著增量逐漸減小，子序列變得更小，最終達到增量為1，整個數組變成一個有序序列，完成排序。這種排序方式使得希爾排序在初始階段，使用較大的步長讓序列更快時間的接近有序，并且減少了不必要的比較與交換。

代碼實現

//希爾排序
void ShellSort(int* a, int n)
{int gap = n;while (gap >= 1){gap /= 2;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}

希爾排序復雜度分析

希爾排序算法的平均時間復雜度通常被認為是介于 O(n log n) 和 O(n^2) 之間，具體取決于所選擇的間隔序列。在最佳情況下，當間隔序列滿足特定條件時，希爾排序可以達到接近 O(n) 的時間復雜度。然而，在最壞情況下，希爾排序的時間復雜度為 O(n^2)。

break;}}a[end + gap] = tmp;}
}

}

## 希爾排序復雜度分析希爾排序算法的平均時間復雜度通常被認為是介于 O(n log n) 和 O(n^2) 之間，具體取決于所選擇的間隔序列。在最佳情況下，當間隔序列滿足特定條件時，希爾排序可以達到接近 O(n) 的時間復雜度。然而，在最壞情況下，希爾排序的時間復雜度為 O(n^2)。