1. 排序匯總
類別 | 排序方法 | 時間復雜度 | 空間復雜度 | 穩(wěn)定性 | ||
平均情況 | 最好情況 | 最壞情況 | ||||
插入排序 | 直接插入 | O(n^2) | O(n) | O(n^2) | O(1) | 穩(wěn)定 |
希爾排序 | O(n^2) | O(n) | O(n^2) | O(1) | 不穩(wěn)定 | |
選擇排序 | 直接選擇 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不穩(wěn)定 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不穩(wěn)定 | |
交換排序 | 冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 穩(wěn)定 |
快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(nlogn) | 不穩(wěn)定 | |
歸并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 穩(wěn)定 | |
2.各個排序面對數(shù)據(jù)的適用情況與小技巧
選取幾個比較有特點有代表性質(zhì)的排序算法
快速排序算法的效率體現(xiàn)在序列越亂的時候，效率越高，當數(shù)據(jù)趨于一個有序狀態(tài)時（無論是順序還是逆序），將會退化為冒泡排序，當數(shù)據(jù)完全處于逆序狀態(tài)時，快速排序?qū)臉O大的時間，因此有些OJ的快速排序模板測試題并不能直接寫快排通過【毒瘤數(shù)據(jù)，超大完全逆序數(shù)據(jù)】，可以嘗試適用rand()產(chǎn)生隨機數(shù)的方法將整體數(shù)據(jù)打亂再使用快速排序，可以極大的減少運行時間。
直接插入排序有著穩(wěn)定和速度快的優(yōu)點，缺點是比較次數(shù)越少，插入點后的數(shù)據(jù)移動就越多，特別是數(shù)據(jù)龐大的時候就需要大量的移動數(shù)據(jù)。
堆排序作為一個相對比較復雜的排序，我們可以更加深入的去借鑒思想，比如有問題要求在n個數(shù)據(jù)中選出或者排序出前k個數(shù)據(jù)，利用堆排序的思維可以不將全部的n進行排序而只操作出前k個數(shù)據(jù)的情況，這個思維是很重要的。
希爾排序最主要的操作是比較而不是交換，因此在小數(shù)組的情況下是比快速排序和堆排序要快的，但是涉及大量數(shù)據(jù)時依舊不如快排。
對于絕大多數(shù)排序在數(shù)據(jù)達到順序的情況下并沒有辦法直接結(jié)束，在前置處理數(shù)據(jù)不是很大的情況下，可以設(shè)置一個flag標記，當數(shù)據(jù)完全處于順序的情況下直接強制退出排序，以達到減少運行時間的效果，當然前置處理數(shù)據(jù)在總執(zhí)行步驟中占比不易過大，如總執(zhí)行100次，在執(zhí)行95次的時候已經(jīng)達到順序，有5次循環(huán)浪費，這樣的情況浪費時間不如你而外增添的標記判斷時間，就不需要這個flag標記。
3. 發(fā)散性思維
上面我們對比切了解到了各種排序的應用情況及優(yōu)缺點，任何一種排序都不是十全十美的，因此我們最好的方式就是揚長避短，那么請你設(shè)計一個算法，能夠主動的通過一次遍歷去發(fā)現(xiàn)數(shù)據(jù)的情況，究竟最適合何種排序為妙呢？
更多訓練見：排序算法專題訓練
| 1169 | 絕對值排序 |
| 1739 | 成績排序 |
| 1756 | 整數(shù)奇偶排序 |
C語言網(wǎng)提供由在職研發(fā)工程師或ACM藍橋杯競賽優(yōu)秀選手錄制的視頻教程，并配有習題和答疑，點擊了解：
一點編程也不會寫的：零基礎(chǔ)C語言學練課程
解決困擾你多年的C語言疑難雜癥特性的C語言進階課程
從零到寫出一個爬蟲的Python編程課程
只會語法寫不出代碼？手把手帶你寫100個編程真題的編程百練課程
信息學奧賽或C++選手的 必學C++課程
藍橋杯ACM、信息學奧賽的必學課程：算法競賽課入門課程
手把手講解近五年真題的藍橋杯輔導課程