基數排序演算法詳解：單鏈表實現版 RadixSort(L, max)

基數排序核心思想與單鏈表實現

基數排序是非比較型排序演算法，時間複雜度可達 O(n)，適合整數排序。本文解析其核心邏輯與單鏈表優化版本。

演算法核心原理

1. 統一位數：將所有待排正整數補齊至相同位數（高位補 0）
2. 從低位到高位：依序對個位、十位、百位……進行穩定排序
3. 桶式分配：每輪按當前位數值（0-9）將元素放入對應桶中
4. 順序收集：按桶序 0→9 將元素取出，形成新序列
5. 重複直至最高位：完成最高位排序後，序列即有序

單鏈表版本 RadixSort(L, max) 優勢

傳統陣列版基數排序需頻繁移動元素；單鏈表版本僅調整指標連接，避免數據搬移，效率更高。此版本需外部傳入最大位數 max，省去掃描鏈表尋找最大值的開銷，比自動計算最大位數的 RadixSort(L) 稍快。

關鍵實現細節

• 使用 10 個桶隊列（頭尾指標），實現先進先出（FIFO）收集
• 每輪分配後，將 10 個桶按序串聯成新鏈表
• 位數提取：(num / radix) % 10，其中 radix 為 1、10、100…
• 空間複雜度 O(n + k)，k=10 為桶數量

適用場景與限制

✅ 適用：大量整數排序、鍵值範圍已知、追求線性時間
❌ 不適用：浮點數、字符串、負數（需轉換）、記憶體極度受限環境

複雜度分析