常見的基礎排序有選擇排序、冒泡排序和插入排序。眾所周知，他們的時間複雜度是 O(n\*n)。 但是，現在要重新認識一下基礎排序演算法，尤其是“插入排序”：在近乎有序的情況下，插入排序的時間複雜度可以降低到 O(n)的程度。 因此，在處理系統日誌的任務中，因為日誌記錄是按照時間排序，但偶爾會有幾條是... ...
文章圖片存儲在GitHub，網速不佳的朋友，請看《基礎排序演算法詳解與優化》 或者 來我的技術小站 godbmw.com
1. 談談基礎排序
常見的基礎排序有選擇排序、冒泡排序和插入排序。眾所周知，他們的時間複雜度是 O(n*n)。
但是，現在要重新認識一下基礎排序演算法，尤其是“插入排序”：在近乎有序的情況下，插入排序的時間複雜度可以降低到 O(n)的程度。
因此，在處理系統日誌的任務中，因為日誌記錄是按照時間排序，但偶爾會有幾條是亂序，此時使用插入排序再好不過。而對於高級排序演算法，一個常見的優化就是利用插入排序做局部數據排序優化。
2. 演算法實現
排序演算法被封裝在了SortBase.h中的SortBase命名空間中，以實現模板化和防止命名衝突。如下圖所示：
2.1 選擇排序
假設從小到大排序，那麼，剛開始指針指向第一個數據，選擇從當前指針所指向數據到最後一個數據間最小的數據，將它放在指針位置。
指針後移一位，重覆上述步驟，直到指針移動到最後一個數據。
這種重覆保證了每次，指針前面的數據都是從小到大排好順序的數據。所以，從頭到尾掃描一遍，自然排好序了。
代碼如下：
template <typename T>
void selectionSort(T arr[], int n) {
int minIndex = -1;
for(int i = 0; i < n; i++) {
minIndex = i;
for(int j = i+1; j < n; ++j) {
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr[i], arr[minIndex]);
}
}2.2 冒泡排序
假設排序是從小到大排序。
我一直感覺冒泡排序是和選擇排序反過來了（如果說錯請指正）。因為選擇排序是每次選擇最小的數據，放到當前指針位置；而冒泡排序是把不停交換相鄰數據，直到把最大的數據“冒泡”到應該到的位置。
優化的地方是：記錄每次交換的最後位置，在此之後的元素在下一輪掃描中均不考慮。因為交換的最後位置之後的元素已經是從小到大排序好了的。
在實現過程中，因為需要不停交換相鄰兩個數據，因此，消耗了很多額外時間。
template <typename T>
void bubbleSort(T arr[], int n) {
int newn;
do {
newn = 0;
for(int i = 1; i < n; i++) {
if(arr[i-1] > arr[i]) {
swap(arr[i-1], arr[i]);
// 優化
newn = i;
}
}
n = newn; // 不再考慮 newn 後的數據
} while (newn > 0);
}2.3 插入排序
插入排序容易和上面兩個演算法搞混。可以類比打撲克牌時候的對撲克牌進行排序：我們會先排序前 1 張、然後是前 2 張、前 3 張 ... 一直到前 n 張。演算法實現顯然是雙重迴圈，如下所示：
template <typename T>
void insertionSort(T arr[], int n) {
for(int i = 1; i < n; i++) {
for(int j = i ; j > 0; j--) {
if(arr[j - 1] > arr[j]) {
swap(arr[j], arr[j - 1]);
} else {
break; // 優化：已經保證之前都是正常排序，直接跳出即可
}
}
}
}顯然，插入排序也能在局部排好序的情況下跳出迴圈（代碼中的優化），以減少演算法消耗時間。
然而上述演算法其實跑分並比不上選擇排序，因為swap(arr[j], arr[j - 1]);這行代碼交換了一次，相當於賦值 3 次，在大數據量情況下，比較消耗時間。
優化: 內層迴圈，每次保存arr[i], 在檢測到當前數據大於arr[i]的時候，後移一位當前元素arr[j] = arr[j-1];。當跳出內層迴圈時，直接將保存的arr[i]賦值給arr[j]即可。
template <typename T>
void insertionSort(T arr[], int n) {
for(int i = 1; i < n; i++) {
T e = arr[i];
int j = i ;
for(; j > 0 && arr[j-1] > e; j--) {
arr[j] = arr[j-1];
}
arr[j] = e;
}
}3. 性能測試
首先利用 SortTestHelper::generateRandomArray函數生成大量無序隨機數據，然後進行排序和時間測定。代碼如下：
#include <iostream>
#include "SortHelper.h"
#include "SortBase.h"
#include "SortAdvance.h"
using namespace std;
int main() {
int n = 50000, left = 0, right = n;
int *arr = SortTestHelper::generateRandomArray<int>(n, left, right);
int *brr = SortTestHelper::copyArray<int>(arr, n);
int *crr = SortTestHelper::copyArray<int>(arr, n);
SortTestHelper::testSort<int>(arr, n, SortBase::selectionSort<int>, "selection sort");
SortTestHelper::testSort<int>(brr, n, SortBase::insertionSort<int>, "insertion sort");
SortTestHelper::testSort<int>(crr, n, SortBase::bubbleSort<int>, "bubble sort");
delete[] brr;
delete[] arr;
delete[] crr;
return 0;
}運行結果如下圖所示：
除了大量無序隨機數據，類似於系統日誌的數據就是基本有序的大量數據。此時，測試代碼如下：
#include <iostream>
#include "SortHelper.h"
#include "SortBase.h"
#include "SortAdvance.h"
using namespace std;
int main() {
int n = 50000, left = 0, right = n;
int *arr = SortTestHelper::generateNearlyOrderedArray<int>(n, 10);
int *brr = SortTestHelper::copyArray<int>(arr, n);
int *crr = SortTestHelper::copyArray<int>(arr, n);
SortTestHelper::testSort<int>(arr, n, SortBase::selectionSort<int>, "selection sort");
SortTestHelper::testSort<int>(brr, n, SortBase::insertionSort<int>, "insertion sort");
SortTestHelper::testSort<int>(crr, n, SortBase::bubbleSort<int>, "bubble sort");
delete[] brr;
delete[] arr;
delete[] crr;
return 0;
}如圖所示，插入排序的只用了 0.002 秒。在這種數據情況下，插入排序的時間複雜度近似 O(N)，絕對快於高級排序的 O(NlogN)。除此之外，還保證了穩定性。
4. 感謝
本篇博客是總結於慕課網的《學習演算法思想 修煉編程內功》的筆記，liuyubobobo 老師人和講課都很 nice，歡迎去買他的課程。
5. 更多內容
- 快速排序和歸併排序：《高級排序演算法實現與優化》
- 堆與堆排序：《堆、堆排序和優先隊列的那些事》
