編碼 · 演算法
計數排序法教學：原理、程式碼與時間複雜度
簡答
計數排序法是一種非比較式排序演算法，適用於範圍已知且較小（大小為 k）的整數（或可對應到整數的鍵值）。它計算每個值出現的次數，用累加和把次數轉成起始位置，再把每個元素直接放到它的位置上。時間為 O(n + k)，額外空間為 O(n + k)。使用前綴和的版本是穩定的，這使它成為基數排序的基礎元件。
開啟行排序計數排序解決什麼問題
任何只比較成對元素的排序法，最差情況都需要 Ω(n log n) 次比較。計數排序完全不做比較，直接拿鍵值本身當陣列索引，因此避開了這個限制。當鍵值是小整數，例如 0 到 100 的考試分數、年齡、0 到 255 的位元組或星等評分，它比任何比較式排序都快。
代價是記憶體用量與鍵值範圍成正比。如果要排序的是幾個分散在整個 64 位元範圍內的整數，就需要大到不可能的計數陣列。
原理與範例
將 [4, 2, 2, 8, 3, 3, 1] 排序，其值落在 0 到 8 的範圍內（k = 9）。
- 計算每個值：
count[v]是 v 出現的次數。 - 前綴和：把每個次數換成小於或等於該值的元素個數。這時
count[v]是 v 所屬位置的最後一格再往後一格。 - 放置元素：從右到左走訪輸入；對每個值 v，先把
count[v]減 1，再把 v 寫入該位置。由右往左走，能讓相等的值維持原本的順序。
| 值 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| 次數 | 0 | 1 | 2 | 2 | 1 | 0 | 0 | 0 | 1 |
| 前綴和 | 0 | 1 | 3 | 5 | 6 | 6 | 6 | 6 | 7 |
因此 1 放到索引 0，兩個 2 放到索引 1 和 2，兩個 3 放到索引 3 和 4，4 放到索引 5，8 放到索引 6。結果：[1, 2, 2, 3, 3, 4, 8]。
Python 實作
這個穩定的版本可依 0 到 k - 1 之間的整數鍵值，排序任何物件。
def counting_sort(items, k, key=lambda x: x):
"""Stable sort of items by integer key in range(k)."""
count = [0] * k
for x in items:
count[key(x)] += 1
for v in range(1, k): # prefix sums
count[v] += count[v - 1]
out = [None] * len(items)
for x in reversed(items): # right to left: stable
count[key(x)] -= 1
out[count[key(x)]] = x
return out
print(counting_sort([4, 2, 2, 8, 3, 3, 1], k=9))
# [1, 2, 2, 3, 3, 4, 8]
people = [("Ana", 3), ("Bo", 1), ("Cy", 3), ("Di", 2)]
print(counting_sort(people, k=4, key=lambda p: p[1]))
# [('Bo', 1), ('Di', 2), ('Ana', 3), ('Cy', 3)]如果只排序單純的整數而且不需要穩定性，有個更簡單的版本，是直接依次數重建輸出。這個變體也能藉由減去最小值的位移來處理負數：
def counting_sort_ints(nums):
if not nums:
return []
lo, hi = min(nums), max(nums)
count = [0] * (hi - lo + 1)
for x in nums:
count[x - lo] += 1
out = []
for offset, c in enumerate(count):
out.extend([offset + lo] * c)
return out
print(counting_sort_ints([3, -1, 2, -1, 0])) # [-1, -1, 0, 2, 3]時間與空間複雜度
| 指標 | 數值 | 原因 |
|---|---|---|
| 時間（任何情況） | O(n + k) | 掃描輸入一次、計數陣列一次、再放置一次 |
| 額外空間 | O(n + k) | 大小為 k 的計數陣列，加上大小為 n 的輸出陣列 |
| 比較次數 | 0 | 鍵值被當作索引使用，而不是互相比較 |
當 k 為 O(n) 時，計數排序是線性的。如果 k 遠大於 n，例如 1,000 個值落在 0 到 10⁹ 的範圍，計數陣列就會成為主要成本，此時比較式排序或基數排序更合適。
計數排序與其他排序法的比較
| 演算法 | 最佳 | 平均 | 最差 | 額外空間 | 穩定 |
|---|---|---|---|---|---|
| 計數排序 | O(n + k) | O(n + k) | O(n + k) | O(n + k) | 是 |
| 基數排序（LSD） | O(d · (n + b)) | O(d · (n + b)) | O(d · (n + b)) | O(n + b) | 是 |
| 合併排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 是 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 否 |
| 堆積排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 否 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 是 |
Timsort（Python 的 sorted） | O(n) | O(n log n) | O(n log n) | O(n) | 是 |
這裡的 k 是鍵值範圍的大小，d 是位數，b 是基數排序使用的基底。使用前綴和並由右往左放置元素時，計數排序是穩定的。簡單的「依次數重建」版本對單純整數會得到相同結果，但無法讓其他資料隨著鍵值一起搬動。
變體與常見錯誤
- 基數排序對每一位數執行一次穩定的計數排序，把這個概念延伸到大整數與固定長度的字串。
- 桶排序（bucket sort）依範圍把值分散到各個桶，再排序每個桶；當值呈均勻分布時很快。
- 只計數、不排序：很多時候你只需要次數，例如建立直方圖或找出眾數。
collections.Counter可以直接做到。
何時使用計數排序
當鍵值是整數，且範圍相較於元素個數很小時就適用：成績、年齡、每月的日期、位元組、0 到 255 的顏色通道值，或小的列舉值。它也是基數排序與後綴陣列建構演算法的內部步驟。面試中，它出現在 Sort Colors（值為 0、1、2）、依頻率排序、H-index 這類題目，以及經典問題：如何突破比較式排序的 O(n log n) 下界。
常見問題
計數排序是穩定的嗎？
是的，使用前綴和並由右往左放置元素的標準版本是穩定的。正是這個性質，讓基數排序能在每一位數上使用它。
計數排序的時間複雜度是多少？
O(n + k)，其中 n 是元素個數，k 是鍵值範圍的大小。最佳、平均與最差情況都相同。
為什麼計數排序能比 O(n log n) 更快？
Ω(n log n) 的下界只適用於比較式排序。計數排序從不比較元素，而是把每個鍵值當作陣列索引，所以不受該下界限制。
計數排序能處理負數嗎？
可以。把每個鍵值減去最小值，讓最小的鍵值對應到索引 0，輸出時再加回去。
什麼時候不該使用計數排序？
當鍵值範圍 k 遠大於 n、鍵值是浮點數或任意字串，或記憶體吃緊時。這時 sorted() 這類比較式排序是更好的選擇。