基礎排序演算法詳解與優化
文章圖片儲存在 GitHub
,網速不佳的朋友,請看 ofollow,noindex" target="_blank">《基礎排序演算法詳解與優化》 或者 來我的技術小站 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. 更多內容
- 快速排序和歸併排序: 《高階排序演算法實現與優化》
- 堆與堆排序: 《堆、堆排序和優先佇列的那些事》