十大排序演算法串講
- 2020 年 11 月 21 日
- 筆記
十大排序演算法串講
各大程式語言為我們內置了sort函數用於排序，其效率要比我們自己實現的排序演算法高效的多（元素為基本數據類型使用快速排序；元素為自定義數據類型使用歸併排序；樣本數量小使用插入排序；樣本數量大先使用快速排序或歸併排序削減規模，後使用插入排序），那我們為什麼還要學習手寫排序演算法呢？
數據結構與演算法是程式設計師的基本功，排序演算法則是基本功中的基本功，我們接觸到的第一個數據結構是數組，第一個演算法則是冒泡排序，企業面試也熱衷於考察面試者是否具備手寫排序演算法的能力；其次排序演算法不單單是用來排序的，許多的經典問題也用到了排序演算法的思想，例如TopK問題（快速排序 | 堆排序）、差值問題（桶排序）、逆序對問題（歸併排序）等等。
對十大排序演算法我們可以大致將其分為三種類型：①冒泡排序、選擇排序、插入排序（程式碼簡單，效率低）；②堆排序、歸併排序、快速排序、希爾排序（程式碼複雜，效率高）；③桶排序、基數排序、計數排序（非比較的排序）。其中堆排序、歸併排序、快速排序尤為重要。
本文將依次講解十大排序演算法的原理，並給出C++版本的程式碼實現。此外要補充的是，排序演算法的穩定性並不是指其時間複雜度是不是穩定的，而是指數組中相同元素在排序前後的相對次序是否保持不變，例如在「姓名-班級-成績」組中先按照成績排序，接著使用穩定排序方法對班級進行排序，則在班級相同的情況下，成績是排好序的，如果使用不穩定的排序方法對班級排序，那麼在班級相同的情況下，成績是亂序的。
冒泡排序
發明人：未知
額外空間複雜度：\(O(1)\)
時間複雜度：\(O(N^2)\)
穩定性：穩定
通過在遍歷時不斷交換元素，讓最大的元素移動到了數組右端，下一次遍歷時便不需要考慮最後一個元素，因為最後一個位置已經確定了。
void BubbleSort(vector<int>& nums) {
for (int i = 0; i < nums.size(); ++i) {
for (int j = 1; j < nums.size() - i; ++j) {
if (nums[j] < nums[j-1]) {
swap(nums[j], nums[j-1]);
}
}
}
}
考慮傳入一個有序數組，上面的程式碼就顯得有些蠢笨了，我們可以適當的修改使得冒泡排序在最好的情況下達到\(O(N)\)的時間複雜度。
void BubbleSort(vector<int>& nums) {
bool flag = true;
for (int i = 0; i < nums.size() && flag; ++i) {
flag = false;
for (int j = 1; j < nums.size() - i; ++j) {
if (nums[j] < nums[j-1]) {
flag = true;
swap(nums[j], nums[j-1]);
}
}
}
}
再考慮數組2,3,4,5,1，雖然數組是基本有序的，但是flag並沒有發揮它的作用，於是冒泡排序有了進一步的改進，稱之為雞尾酒排序，或雙向冒泡排序。
void BubbleSort(vector<int>& nums) {
int l = 0, r = nums.size()-1;
bool flag = true;
while (l < r && flag) {
flag = false;
for (int i = l; i <= r; ++i) {
for (int j = l + 1; j <= r - i; ++j) {
if (nums[j] < nums[j-1]) {
flag = true;
swap(nums[j], nums[j-1]);
}
}
}
--r;
for (int i = r; i >= l; --i) {
for (int j = r - 1; j >= l; --j) {
if (nums[j] > nums[j+1]) {
flag = true;
swap(nums[j], nums[j+1]);
}
}
}
++l;
}
}
選擇排序
發明人：未知
額外空間複雜度：\(O(1)\)
時間複雜度：\(O(N^2)\)
穩定性：不穩定
通過遍歷尋找剩餘元素中的最小元素，並將其移動到數組左端，下一次遍歷時便不需要考慮第一個元素，因為第一個位置已經確定了。
選擇排序是十大排序演算法里最菜的，不僅時間複雜度高還不穩定，其實選擇排序也可以雙向選擇，但是大可不必為了提升的那一點點性能讓程式碼變得更加複雜還難以理解。
void SelectSort(vector<int>& nums) {
for (int i = 0; i < nums.size(); ++i) {
int m = i;
for (int j = i + 1; j < nums.size(); ++j) {
if (nums[j] < nums[m]) {
m = j;
}
}
swap(nums[i], nums[m]);
}
}
插入排序
發明人：Herman Hollerith
額外空間複雜度：\(O(1)\)
時間複雜度：\(O(N^2)\)
最好時間複雜度：\(O(N)\)
穩定性：穩定
對於當前元素，向前尋找合適位置插入，在遍歷的過程中數組前端一直保持有序狀態。
void InsertSort(vector<int>& nums) {
for(int i = 1; i < nums.size(); ++i) {
int j, basic = nums[i];
for(j = i; j > 0 && nums[j-1] > basic; --j) {
nums[j] = nums[j-1];
}
nums[j] = basic;
}
}
雖然插入排序與冒泡排序、選擇排序同屬簡單排序，但是插入排序在數據規模小或數據基本有序時是一個非常不錯的選擇。
在STL的sort演算法和stdlib的qsort演算法中，都將插入排序作為快速排序的補充，用於少量元素的排序（通常為8個或以下）。究其原因在於插入排序時間複雜度常數項是小於快速排序時間複雜度常數項的，設插入排序時間複雜度為\(O(CI\times{N^2})\)，快速排序時間複雜度為\(O(CQ\times{N\log{N}})\)，即當\(CI\times{N^2} < CQ\times{N\log{N}}\)使用插入排序會更快。
上面程式碼在向前尋找合適位置插入的過程中，是遍歷尋找的，這裡可以使用二分法優化。二分法插入排序的時間複雜度是要遠低於普通插入排序的（我用這段程式碼AC了卡\(O(N^2)\)排序的題目），但還沒有到\(O(N\log{N})\)。
void InsertSort(vector<int>& nums) {
for (auto i = nums.begin(); i != nums.end(); ++i) {
auto j = lower_bound(nums.begin(), i, *i);
rotate(j, i, i+1);
}
}
堆排序
發明人：Robert W．Floyd
額外空間複雜度：\(O(1)\)
時間複雜度：\(O(N\log{N})\)
穩定性：不穩定
堆是一顆二叉樹，可以用數組來表示，大頂堆即每個節點的值都大於它的子節點。我們每一次都拿出堆的根節點，即最大值，放到數組的後端。這樣當堆的大小為0時，整個數組就已經升序排列完成了。
void HeapSort(vector<int>& nums) {
// 構建大頂堆
for (int i = 0; i < nums.size(); ++i) {
int c = i, p = (c-1)/2;
while (nums[c] > nums[p]) {
swap(nums[c], nums[p]);
c = p;
p = (c-1)/2;
}
}
int size = nums.size();
while (size) {
// 根節點與末節點交換
swap(nums[0], nums[--size]);
// 根節點下沉，使其符合大頂堆的特性
int c = 0, l = 2*c+1;
while (l < size) {
int r = l + 1;
int g = r < size && nums[l] < nums[r] ? r : l;
if (nums[c] >= nums[g]) {
break;
} else {
swap(nums[c], nums[g]);
c = g;
l = 2*c+1;
}
}
}
}
歸併排序
發明人：John von Neumann
額外空間複雜度：\(O(N)\)
時間複雜度：\(O(N\log{N})\)
穩定性：穩定
將數組劃分為兩部分，令其分別有序，再將兩部分合併，使整段區間有序。
void MergeSort(vector<int>& nums, int l, int r) {
if (l >= r - 1) return;
int m = (l + r) / 2;
MergeSort(nums, l, m);
MergeSort(nums, m, r);
// merge
int i = 0, p1 = l, p2 = m;
vector<int> help(r-l);
while (p1 < m && p2 < r) {
help[i++] = nums[p1] < nums[p2] ? nums[p1++] : nums[p2++];
}
while (p1 < m) {
help[i++] = nums[p1++];
}
while (p2 < r) {
help[i++] = nums[p2++];
}
for (int j = 0; j < r-l; ++j) {
nums[l+j] = help[j];
}
}
快速排序
發明人：C. A. R. Hoare
額外空間複雜度：\(O(\log{N})\)
時間複雜度：\(O(N\log{N})\)
穩定性：不穩定
將數組劃分為三部分，左邊全部小於某個值，中間全部等於某個元素值，右邊全部大於某個元素值。接著遞歸劃分左右部分。
void QuickSort(vector<int>& nums, int l, int r) {
if (l >= r-1) return;
int basic = nums[l];
// 計算斷點m, n
int i = l, m = l, n = r;
while (i < n) {
if (nums[i] < basic) {
swap(nums[i++], nums[m++]);
} else if(nums[i] > basic) {
swap(nums[i], nums[--n]);
} else {
++i;
}
}
QuickSort(nums, l, m);
QuickSort(nums, n, r);
}
希爾排序
發明人：Donald L. Shell
額外空間複雜度：\(O(1)\)
最壞時間複雜度：\(O(N^2)\)
最好時間複雜度：\(O(N)\)
穩定性：不穩定
每一次根據不同的步長將子序列進行排序。步長越大，子序列越短且越無序；步長越小，子序列越長且越有序。希爾排序使用插入排序法對子序列進行排序，因為無序時元素少，元素多時基本有序的特點，插入排序充分的發揮了它的優勢。
void ShellSort(vector<int>& nums) {
for (int step = nums.size() / 2; step > 0; step /= 2) {
for (int begin = 0; begin < step; ++begin) {
for (int i = begin + step; i < nums.size(); i += step) {
int j, basic = nums[i];
for (j = i; j > begin && nums[j-step] > basic; j -= step) {
nums[j] = nums[j-step];
}
nums[j] = basic;
}
}
}
}
桶排序
發明人：未知
額外空間複雜度：\(O(N+K)\)
時間複雜度：\(O(N+K)\)
穩定性：穩定
與其說是一種排序演算法，不如說是一種思想，基數排序和計數排序都是桶思想的實現。通過上面給出的圖片不難理解，桶排序就是數據範圍分割為不同段，再在各段內進行排序，最後合併到一起就是有序的序列。
對於如何令各個桶分別有序，可以採用遞歸或其他的排序演算法來進行，這裡就以庫排序函數來演示，主要體現的是通過桶來降低數據規模的思想。假設數據範圍在0到99，共設10個桶，每個桶的範圍為10。
void BucketSort(vector<int>& nums) {
vector<vector<int>> help(10, vector<int>(0));
for (auto i : nums) {
help[i/10].push_back(i);
}
int i = 0;
for (auto v : help) {
sort(v.begin(), v.end());
for (auto j : v) {
nums[i++] = j;
}
}
}
計數排序
發明人：Harold H. Seward
額外空間複雜度：\(O(N+K)\)
時間複雜度：\(O(N+K)\)
穩定性：穩定
計數排序運用了桶的思想，是非比較的排序，適用於數據量大但數據範圍小的情況。需要注意的是help數組的長度。舉個例子，數據範圍在100-200，如果把help的大小開到200，那麼有一半的空間是浪費的，因此需要對下標做一個轉換。
void CountSort(vector<int>& nums) {
int l = *min_element(nums.begin(), nums.end());
int h = *max_element(nums.begin(), nums.end());
int n = h - l + 1, k = 0;
vector<vector<int>> help(n, vector<int>(0));
for (auto i : nums) {
help[i-l].push_back(i);
}
for (int i = l; i <= h; ++i) {
if (0 == help[i-l].size()) continue;
for (auto j : help[i-l]) {
nums[k++] = j;
}
}
}
上面程式碼將help開成了二維數組，是為了保證排序的穩定性，還有一種巧妙地方法是使用前綴數組，免去了vector動態擴容帶來的額外負擔。
舉個例子，nums = {7,4,3,4,7,8,7,5,6}，help = {1,3,4,5,8,9}，我們逆序遍歷nums，對於nums[6] == 7這個元素，對應的help[7-min(nums)]就是這個7應該在排序後的數組中的位置，接著help[7-min(nums)]做自減運算，變成nums[4] == 7在排序後的數組中的位置。
void CountSort(vector<int>& nums) {
int l = *min_element(nums.begin(), nums.end());
int h = *max_element(nums.begin(), nums.end());
vector<int> help(h-l+1, 0);
vector<int> result(nums.size());
for (auto i : nums) {
++help[i-l];
}
for (int i = 1; i < h-l+1; ++i) {
help[i] += help[i-1];
}
for (auto i = nums.rbegin(); i != nums.rend(); ++i) {
result[--help[*i-l]] = *i;
}
nums = result;
}
基數排序
發明人：Herman Hollerith
額外空間複雜度：\(O(N+K)\)
時間複雜度：\(O(N\times{K})\)
穩定性：穩定
基數排序運用了桶的思想，是非比較的排序，先按照最末位排序，再按照次末位排序...直到按照最高位排好序。在排序前需要先求出所有元素的最大位數。
void RadixSort(vector<int>& nums) {
int d = 0;
for (auto i : nums) {
int c = 1;
while (i /= 10) ++c;
d = max(c, d);
}
for (int k = 0; k < d; ++k) {
vector<vector<int>> help(10, vector<int>(0));
for (auto i : nums) {
int j = 0, n = i;
for (int t = 0; t <= k; ++t) {
j = n % 10;
n /= 10;
}
help[j].push_back(i);
}
int j = 0;
for (auto v : help) {
for (auto i : v) {
nums[j++] = i;
}
}
}
}
與計數排序類似，基數排序也可以通過前綴數組進行優化，但是和計數排序相比，因為要計算第i位上的數字，程式碼會更複雜一點。
void RadixSort(vector<int>& nums) {
int d = 0;
for (auto i : nums) {
int c = 1;
while (i /= 10) ++c;
d = max(c, d);
}
for (int k = 0; k < d; ++k) {
vector<int> help(10);
vector<int> result(nums.size());
for (auto i : nums) {
int j = 0, n = i;
for (int t = 0; t <= k; ++t) {
j = n % 10;
n /= 10;
}
++help[j];
}
for (int i = 1; i < 10; ++i) {
help[i] += help[i-1];
}
for (auto i = nums.rbegin(); i != nums.rend(); ++i) {
int j = 0, n = *i;
for (int t = 0; t <= k; ++t) {
j = n % 10;
n /= 10;
}
result[--help[j]] = *i;
}
nums = result;
}
}
總結一下，十大排序演算法中，堆排序、歸併排序、快速排序需要完全理解並掌握，其中涉及了堆數據結構、分治和遞歸思想。桶排序、計數排序、基數排序的適用範圍有限，主要是去掌握它的思想。
本文圖源：visualgo，algorithm visualizer
