排序（四）排序優化
幾種排序算法
| 時間複雜度 | 是否穩定 | 是否原地排序 | |
|---|---|---|---|
| 冒泡排序 | O(n²) | 穩定 | 是 |
| 插入排序 | O(n²) | 穩定 | 是 |
| 選擇排序 | O(n²) | 不穩定 | 是 |
| 快速排序 | O(nlogn) | 不穩定 | 是 |
| 歸併排序 | O(nlogn) | 穩定 | 不是 |
| 計數排序 | O(n+k),k是數據範圍 | 穩定 | 不是 |
| 桶排序 | O(n) | 穩定 | 不是 |
| 基數排序 | O(dn),d是維度 | 穩定 | 不是 |
排序算法的選擇
雖然線性排序時間複雜度比較低，但是適用場景特殊條件苛刻，所以不能選用線性排序作為通用排序算法。
對於小規模數據可以選擇時間複雜度為O(n²)的算法，在小規模數據面前，O(n2) 時間複雜度的算法並不一定比 O(nlogn) 的算法執行時間長；對於大規模的數據，可以選用時間複雜度為O(nlogn)的算法。為了兼顧任意規模的數據，會選擇時間複雜度為O(nlogn)的算法，其中包括：歸併排序、快速排序、堆排序等。
歸併排序在平均、最壞時間複雜度上都為O(nlogn),但是歸併排序不是原地排序，當需要排序的數據比較大時，就為佔用額外過多內存，顯然不合適。快速排序是原地排序，但最壞情況時間複雜度退化為O(n²)。
優化快速排序
分區點：選取分區點不夠合理，導致數據全部分到一邊，時間複雜度就會變為O(n²)，所以優化的關鍵在於分區點的選取。
- 三數取中法：取開頭、結尾和中間數據，求平均值作為分區點
- 隨機發：從概率學的角度，不太可能出現每次都選到最差分區點的情況
遞歸問題：快速排序是用遞歸實現的，遞歸過程中可能出現堆棧溢出。
- 限制遞歸深度
- 在堆上手動模擬一個函數調用棧，手動模擬遞歸入棧出棧，這樣就沒有棧大小限制（堆是內存中最大的一塊）
