Sorting · 比較表
排序演算法比較
八種排序演算法的時間、空間、穩定性、是否原地，以及最重要的：什麼情況該選哪一個。
| 演算法 | 時間 | 空間 | 最好 | 最壞 | 穩定 | 原地 | 難度 |
|---|---|---|---|---|---|---|---|
| Bubble Sort氣泡排序 | O(n²) | O(1) | O(n) | O(n²) | ✓ | ✓ | 入門 |
| Selection Sort選擇排序 | O(n²) | O(1) | O(n²) | O(n²) | ✗ | ✓ | 入門 |
| Insertion Sort插入排序 | O(n²) | O(1) | O(n) | O(n²) | ✓ | ✓ | 入門 |
| Merge Sort合併排序 | O(n log n) | O(n) | O(n log n) | O(n log n) | ✓ | ✗ | 進階 |
| Quick Sort快速排序 | 平均 O(n log n) | O(log n) | O(n log n) | O(n²) | ✗ | ✓ | 進階 |
| Heap Sort堆積排序 | O(n log n) | O(1) | O(n log n) | O(n log n) | ✗ | ✓ | 進階 |
| Counting Sort計數排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | ✓ | ✗ | 進階 |
| Radix / Bucket Sort基數與桶排序 | O(d·n) | O(n+k) | O(d·n) | O(d·n) | ✓ | ✗ | 進階 |
什麼時候選哪一個
Bubble Sort 氣泡排序
教學、資料只有幾十筆、或想順便數逆序對。實務上幾乎不選。
Selection Sort 選擇排序
寫入很貴（EEPROM、flash）：交換次數最多 n−1 次，是所有排序裡最少的。
Insertion Sort 插入排序
資料幾乎有序、或很小（n < 16）。快速排序與 Timsort 的小段落都交給它收尾。
Merge Sort 合併排序
需要穩定、需要最壞情況保證、或資料放不進記憶體（外部排序）、鏈結串列。
Quick Sort 快速排序
一般用途的預設：常數最小、cache 友善。記得隨機選 pivot 避免最壞情況。
Heap Sort 堆積排序
要 O(n log n) 保證又不能多用記憶體（嵌入式、即時系統）。比快速排序慢 2 到 3 倍。
Counting Sort 計數排序
鍵是小範圍整數（分數 0–100、字元、年齡）。k 比 n log n 小就贏。
Radix / Bucket Sort 基數與桶排序
固定位數的整數或字串（電話號碼、ID、日期），n 很大時比 O(n log n) 快。
選擇指南
- 不知道選什麼：語言內建的 sort。它通常是 Timsort（Python、Java 物件）或 introsort（C++），已經幫你混合了合併、插入、堆積。
- 同分要保持原順序：穩定的那幾個——合併、插入、計數、基數。快速與堆積排序不穩定。
- 鍵是小整數：計數排序或基數排序，這是唯一能打破 n log n 下界的方法，因為它們不靠比較。
- 幾乎已排序：插入排序 O(n)。氣泡加提前結束也行，但小值在尾端時會退化。
- 記憶體很緊：堆積排序（O(1) 額外空間、保證 n log n）或快速排序（O(log n) 堆疊）。合併排序要多一份 O(n)。
- 資料放不進記憶體：合併排序，一次讀一段、排好寫出去、最後多路合併。