排序演算法是電腦科學的基石。本文系統梳理六大類內部排序策略，附帶偽碼、複雜度分析與適用場景，幫助你在面試、系統設計或效能調優時精準選型。
對每個元素統計「有多少元素比它小」以決定最終位置。雙重迴圈，時間 O(n²)、空間 O(n)，不移動記錄但效率極低，僅具教學意義。
假設資料範圍 [min, max]，建立計數陣列 count[min..max] 統計頻次，再做前綴和轉為位置索引。零比較、時間 O(n + k)（k = max-min+1）、空間 O(k)，適合「範圍小、整數鍵值」場景，是基數排序的雛形。
外層掃描無序區，內層從有序區尾部向前比較位移。最壞（逆序）O(n²)，平均 O(n²/4)，近乎有序資料最快，常作為複雜演算法（如 Shell、Quick）小區間的基底排序。
用二分搜尋定位插入點，比較次數降為 O(log n)，但位移成本仍為 O(n)，總體複雜度不變。
分組插入的推廣：依遞減增量序列（如 8,4,2,1 或 2^k-1）分組插入，打破「單步位移」瓶頸。增量序列選擇直接影響效能，理論最優 O(n^{3/2})，工程上常用 Ciura 序列 或 Sedgewick 序列。
相鄰比較交換，最大元素「浮」到右端。優化：記錄最後交換位置縮減邊界、無交換提前終止。教學用途為主。
分治法核心：選樞軸，O(n) 分區使左 < 樞軸 < 右，遞迴處理子區。平均 O(n log n)、最壞 O(n²)（可用隨機樞軸或三數取中緩解）。比較類排序中平均效能最強，工程實作常於小區間（< 8~16）切換插入排序。
按二進制位從高到低分區（0 左、1 右），遞迴處理。時間 O(n log U)（U 為最大值位寬），常數因子略優於 Quick Sort，但實作較繁瑣。
每輪掃描選最小值與首位交換。比較次數固定 n(n-1)/2、交換 O(n)，優於 Bubble Sort 交換次數。
鍵盤賽制建立勝者樹，根節點為極值。輸出後將該葉設為 -∞，沿路徑重算，第二極值只需 log n 比較。需額外空間存樹、引入 -∞ 哨兵。
以陣列隱式存儲完全二元樹（大根堆），O(n) 建堆，再重複「交換堆頂與尾端、縮減堆大小、下沉調整」。最壞/平均皆 O(n log n)、空間 O(1)、無最壞情況退化。缺點：快取命中率低、小 n 時常數因子大。天然支援優先佇列（插入、刪最大、修改鍵值均 O(log n)）。
遞迴二分至單元素，再兩兩合併有序子陣列。時間穩定 O(n log n)、穩定排序、適合連結串列與外部排序。工程上常「自底向上」迭代實作、小區間用插入排序啟動。
多關鍵字（如百/十/個位）從最低位 (LSD) 到最高位 (MSD) 依次「分桶→收集」。零比較、時間 O(d(n+k))（d 關鍵字數、k 桶數）、空間 O(n+k)。關鍵優化：首掃統計各桶計數 → 計算前綴和得起始索引 → 精確搬移，將空間從 O((k+1)n) 壓縮至 O(n+k)。適用於「固定長度整數/字串、鍵值範圍可控」場景。
| 演算法 | 平均時間 | 最壞時間 | 空間 | 穩定 | 適用場景 |
|---|---|---|---|---|---|
| Direct Insertion | O(n²) | O(n²) | O(1) | 是 | 微型/近乎有序資料 |
| Shell Sort | ~O(n^{1.3}) | O(n²) | O(1) | 否 | 中等規模、嵌入式環境 |
| Quick Sort | O(n log n) | O(n²) | O(log n) | 否 | 通用高效排序首選 |
| Heap Sort | O(n log n) | O(n log n) | O(1) | 否 | 嚴格最壞情況保證、優先佇列 |
| Merge Sort | O(n log n) | O(n log n) | O(n) | 是 | 穩定需求、連結串列、外部排序 |
| Radix Sort | O(d(n+k)) | O(d(n+k)) | O(n+k) | 是 | 整數/定長字串、鍵值範圍小 |
沒有「最快」的排序，只有「最適合資料特徵與約束條件」的排序。掌握上述演算法的核心權衡，才能在真實工程中做出最優決策。
