排序演算法#
排序是演算法學習的基石，幾乎所有程式語言都內建排序函式。掌握排序演算法不僅能應對面試，更能理解演算法設計的核心思想。
章節概覽#
| 分類 | 演算法 | 時間複雜度 | 空間複雜度 | 穩定性 |
|---|---|---|---|---|
| 基礎排序 | 冒泡、插入、選擇 | O(n²) | O(1) | 冒泡/插入穩定 |
| 進階排序 | 歸併、快速 | O(n log n) | O(n) / O(log n) | 歸併穩定 |
| 線性排序 | 桶、計數、基數 | O(n) | O(n) | 視實作而定 |
如何分析排序演算法#
分析排序演算法需要從三個維度考量：
執行效率
- 最好、最壞、平均時間複雜度
- 係數、常數、低階項（小規模資料時很重要）
- 比較次數與交換/移動次數
記憶體消耗
- 空間複雜度 O(1) 稱為「原地排序」(In-place)
穩定性
- 相等元素排序後是否保持原有順序
- 多欄位排序時，穩定性至關重要
工業級排序函式（如 C 的 qsort、Java 的 Arrays.sort）通常混合使用多種演算法，根據資料規模動態選擇最優策略。