基數排序

🎯 什麼情境該想到我

當你「要排大量的整數、固定長度字串、IP、日期、定長 ID」的時候。
★ 它把計數排序的「值域不能大」限制解掉了——代價是輸入必須能被拆成幾個位數。

⚙️ 怎麼用（機制與推導）

運作機制：LSD（從最低位開始）

輸入：329  457  657  839  436  720  355

① 排個位數（穩定排序）
   720  355  436  457  657  329  839
     ↑0   ↑5   ↑6   ↑7   ↑7   ↑9   ↑9
                    ★ 457 在 657 前面 —— 因為上一輪它就在前面（穩定性）

② 排十位數
   720  329  436  839  355  457  657

③ 排百位數
   329  355  436  457  657  720  839    ← 完成

// 排非負整數，base 通常取 256（每輪處理一個 byte）
func RadixSort(a []uint32) {
    const base = 256
    buf := make([]uint32, len(a))
    for shift := 0; shift < 32; shift += 8 {
        var count [base]int
        for _, v := range a {
            count[(v>>shift)&(base-1)]++
        }
        for i := 1; i < base; i++ {
            count[i] += count[i-1]
        }
        // ★ 從後往前 —— 穩定性
        for i := len(a) - 1; i >= 0; i-- {
            d := (a[i] >> shift) & (base - 1)
            count[d]--
            buf[count[d]] = a[i]
        }
        a, buf = buf, a           // 交換角色，省掉一次 copy
    }
    // 32/8 = 4 輪（偶數），結果正好回到 a
}

★ 為什麼「必須從最低位開始」而且「必須用穩定排序」

這是這題唯一真正的考點。

LSD 的正確性完全依賴穩定性。

排到第 $i$ 位時，前 $i - 1$ 位已經排好了。
穩定排序保證：第 $i$ 位相同的元素，維持它們原本（也就是低位已排好）的相對順序。
所以每一輪結束後，「後 $i$ 位」都是正確排序的。

如果內層排序不穩定，低位的排序成果在高位那一輪就會被打亂，整個演算法錯誤。

為什麼不從高位開始（MSD）：MSD 也可行，但每個前綴群組要各自遞迴，需要管理大量子問題的邊界——
實作複雜得多。好處是可以提前結束（前綴已經區分出來就不用往下排），所以變長字串排序用 MSD。

	LSD	MSD
方向	低位 → 高位	高位 → 低位
需要穩定內層	✅ 必須	不需要
實作	簡單（迴圈）	複雜（遞迴 + 分組）
提前結束	❌ 一定要跑完所有位	✅
適合	定長整數	變長字串

複雜度

$Θ (d \cdot (n + b))$

$d$ = 位數（以基底 $b$ 計）
$b$ = 基底（每輪的值域）

基底的取捨：

base	32 位元整數的輪數 $d$	每輪 count 陣列
10	10	10
256（1 byte）	4	256 ← 實務常用
65536（2 bytes）	2	65,536

★ base 越大輪數越少，但 count 陣列越大（可能超出快取）。
256 是常見的甜蜜點：正好一個 byte，位移與遮罩都是單一指令，count 陣列 1 KB 完全在 L1 快取內。

什麼時候真的比快排快

$n$ 很大（ $1 0^{6}$ 以上）
鍵是定長整數
實測上常見 2–3 倍的差距（但必須自己量，取決於資料與硬體）

🧪 我實際套用的紀錄

（待填）

⚠️ 注意 / 什麼時候不適用

★ 有符號整數要先處理。直接對負數的二補數表示做位元比較會錯（負數的最高位是 1，會被排到後面）。標準做法是把最高位翻轉（v ^ 0x80000000）再排。
浮點數也可以排，但要轉換：IEEE 754 正數可直接比位元，負數要整個翻轉。這是個有名的技巧，但容易寫錯。
變長字串用 MSD，或先補齊到定長（補齊會浪費空間）。
★ $Θ (d n)$ 不是「線性」。 $d$ 對 32 位元整數是 4，對 128 位元 UUID 是 16—— $d$ 會吃掉優勢。
要 $Θ (n)$ 的額外空間（輸出緩衝區）。
★ 實務上幾乎不用自己寫。標準庫的排序已經高度優化且泛用；基數排序只在明確量測到排序是瓶頸、且鍵是定長整數時才值得。
內層一定要穩定（見上面的推導）。

🔗 相關工具

計數排序 —— 內層使用的演算法，以及「穩定性為什麼是前提」
快速排序 —— 通用的對照組
雜湊表 —— 同屬「把鍵的結構拿來直接定位」的思路
演算法導論

Quartz 5

Explorer