每個檔案都是獨立、可編譯執行的示範程式，內含：原理註解、複雜度分析、
穩定性說明、多組測試（含空陣列、單元素、已排序、反向、重複元素等邊界情況）。
編譯方式
g++ -std=c++17 -O2 -Wall -o <name> <name>.cpp && ./<name>
演算法總覽
基礎比較排序 O(n²)
| 檔案 |
演算法 |
最好 |
平均 / 最壞 |
穩定 |
特點 |
bubble_sort.cpp |
泡沫排序 |
O(n) |
O(n²) |
穩定 |
提早結束優化 |
selection_sort.cpp |
選擇排序 |
O(n²) |
O(n²) |
不穩定 |
交換最多 n−1 次 |
insertion_sort.cpp |
插入排序 |
O(n) |
O(n²) |
穩定 |
近乎有序時極快；含二分插入版 |
gnome_sort.cpp |
地精排序 |
O(n) |
O(n²) |
穩定 |
程式碼極短 |
cycle_sort.cpp |
循環排序 |
O(n²) |
O(n²) |
不穩定 |
寫入次數理論最少 |
comb_sort.cpp |
梳排序 |
O(n log n) |
O(n²) |
不穩定 |
泡沫排序 + 縮減間距 |
高效比較排序 O(n log n)
| 檔案 |
演算法 |
最好 |
平均 |
最壞 |
穩定 |
特點 |
shell_sort.cpp |
希爾排序 |
O(n log n) |
~O(n^1.5) |
視 gap |
不穩定 |
Knuth gap 序列 |
merge_sort.cpp |
合併排序 |
O(n log n) |
O(n log n) |
O(n log n) |
穩定 |
含遞迴 + 自底向上兩版 |
quick_sort.cpp |
快速排序 |
O(n log n) |
O(n log n) |
O(n²) |
不穩定 |
Lomuto / Hoare / 隨機 pivot / 三路切分 |
heap_sort.cpp |
堆積排序 |
O(n log n) |
O(n log n) |
O(n log n) |
不穩定 |
原地、無退化 |
tree_sort.cpp |
樹排序 |
O(n log n) |
O(n log n) |
O(n²) |
穩定 |
BST 中序走訪 |
非比較排序（線性時間）
| 檔案 |
演算法 |
時間 |
空間 |
穩定 |
限制 |
counting_sort.cpp |
計數排序 |
O(n + k) |
O(n + k) |
穩定 |
整數、值域 k 不能太大 |
radix_sort.cpp |
基數排序 (LSD) |
O(d·(n + b)) |
O(n + b) |
穩定 |
整數／定長字串；含負數處理 |
bucket_sort.cpp |
桶排序 |
平均 O(n + k) |
O(n + k) |
視桶內排序 |
資料需大致均勻分佈 |
工業級混合排序
| 檔案 |
演算法 |
時間 |
穩定 |
誰在用 |
intro_sort.cpp |
內省排序 |
O(n log n) 保證 |
不穩定 |
C++ std::sort（Quick + Heap + Insertion） |
tim_sort.cpp |
Tim 排序（簡化版） |
最好 O(n)，最壞 O(n log n) |
穩定 |
Python sorted()、Java 物件排序（Merge + Insertion） |
如何選擇
- 一般用途：直接用
std::sort（Intro Sort）；需要穩定用 std::stable_sort。
- 資料幾乎有序：插入排序（小量）或 Tim Sort。
- 整數且值域小：計數排序；值域大改基數排序。
- 記憶體極度受限：堆積排序（原地、O(n log n) 保證）。
- 寫入昂貴（flash/EEPROM）：循環排序或選擇排序。
- 大量重複元素：三路快速排序（見
quick_sort.cpp）。
- 外部排序（資料超過記憶體）：合併排序的分段合併思想。
所有程式皆以 g++ -std=c++17 -O2 -Wall -Wextra 編譯通過並驗證輸出正確
（intro_sort 與 tim_sort 另以 10 萬～20 萬筆隨機資料與
std::sort / std::stable_sort 對拍驗證）。