🎯 什麼情境該想到我
當你「要排的是整數，而且值域不大」的時候——年齡、分數、狀態碼、月份、評分。
★ 它是線性時間的，而理解「它憑什麼突破 」比記住它本身更重要。
⚙️ 怎麼用（機制與推導）
★ 先搞懂： 的下界是怎麼來的
比較排序（只靠「 嗎」來決定順序）可以畫成一棵決策樹：
- 每個內部節點是一次比較，兩個分支是「是／否」
- 每個葉節點是一種可能的輸出排列
個元素有 種排列 → 樹至少要有 個葉節點 → 高度（最差比較次數）至少 。
由 Stirling 近似 ：
★ 關鍵字是「比較」。
這個下界的前提是「你只能透過比較獲得資訊」。
計數排序不做比較——它直接把「值」當成「陣列索引」用。
它不是打破了數學定理，而是根本不在定理的適用範圍內。
運作機制
輸入 a = [2, 5, 3, 0, 2, 3, 0, 3]，值域 k = 6（0..5）
① 統計每個值出現幾次
count = [2, 0, 2, 3, 0, 1]
0 1 2 3 4 5
② ★ 改成「前綴和」：count[v] = 有幾個元素 ≤ v
count = [2, 2, 4, 7, 7, 8]
↑ 值為 3 的元素，最後一個該放在索引 6（=7-1）
③ ★ 從後往前掃輸入，放進輸出陣列
（從後往前是「穩定」的關鍵）
// a 的元素都在 [0, k)
func CountingSort(a []int, k int) []int {
count := make([]int, k)
for _, v := range a {
count[v]++
}
// 前綴和：count[v] = 有幾個元素 <= v
for v := 1; v < k; v++ {
count[v] += count[v-1]
}
out := make([]int, len(a))
// ★ 一定要從後往前，否則不穩定
for i := len(a) - 1; i >= 0; i-- {
count[a[i]]--
out[count[a[i]]] = a[i]
}
return out
}★ 「從後往前」為什麼是穩定性的關鍵
count[v] 記錄的是「值為 的元素該放的最後一個位置」。
從後往前掃，輸入中較後面的元素先被放進較後面的位置 → 相對順序保持不變。
如果從前往後掃，先掃到的元素會被放進後面的位置 → 相等元素的順序被反轉。
★ 這不是細節，是 基數排序 能運作的唯一前提。
基數排序靠「先排低位、再排高位」，而高位排序時必須保住低位已經排好的順序——
沒有穩定性，基數排序完全是錯的。
複雜度
| 時間 | |
| 空間 | |
| 穩定 | ✅（靠從後往前） |
| 原地 | ❌ |
★ 什麼時候真的是「線性」：只有當 時，。
（排 32 位元整數）而 時，它比任何比較排序都慢得多——而且會配置 4 GB 記憶體。
🧪 我實際套用的紀錄
- （待填）
⚠️ 注意 / 什麼時候不適用
- ★ 值域 決定一切。 時完全不能用。使用前先算
max - min。 - 值域可以平移。值在
[100000, 100100]時，開k = 101的陣列並減去min即可——不要開 100101 大小的陣列。 - 只能排「能當索引」的東西：非負整數（或可映射成整數的：列舉、字元、日期序號）。浮點數、任意字串不行。
- 負數要先平移。
- 一定要從後往前掃，否則穩定性沒了，
基數排序會跟著壞掉。 - 實務上很少單獨使用。真正的價值是當 基數排序 的內層，以及桶排序類的前置步驟。
- 值域很大但分布集中時，考慮桶排序（bucket sort）而非計數排序。