基數排序法教學：原理、程式碼與時間複雜度

基數排序解決什麼問題

計數排序是線性的，但需要與整個鍵值範圍一樣大的計數陣列，這對 32 位元或 64 位元整數是不可能的。基數排序把每個鍵值拆成小的位數，每個位數執行一次計數排序，所以每一回合只需要 b 個項目的計數陣列（十進位位數為 10，位元組為 256）。

任何能拆成固定長度小符號序列的鍵值都適用：非負整數、寫成 YYYYMMDD 的日期、郵遞區號之類的固定長度代碼、IP 位址，以及固定寬度的字串。

範例：十進位的 LSD 基數排序

將 [170, 45, 75, 90, 802, 24, 2, 66] 排序。最大的數有 3 位，所以要進行 3 回合。每一回合都是依單一位數做穩定排序：位數相同的元素保持上一回合的順序。

第 2 回合後，數字已依最後兩位排好序。在第 3 回合，2、24、45、66、75 和 90 的百位數都是 0，穩定性讓它們維持第 2 回合產生的順序。這就是每一回合都必須穩定的原因。

Python 實作

def counting_pass(nums, exp, base):
    """Stable counting sort of nums by the digit at exp."""
    count = [0] * base
    for x in nums:
        count[(x // exp) % base] += 1
    for d in range(1, base):
        count[d] += count[d - 1]
    out = [0] * len(nums)
    for x in reversed(nums):
        d = (x // exp) % base
        count[d] -= 1
        out[count[d]] = x
    return out

def radix_sort(nums, base=10):
    """LSD radix sort for non-negative integers."""
    if not nums:
        return []
    exp, biggest = 1, max(nums)
    while biggest // exp > 0:
        nums = counting_pass(nums, exp, base)
        exp *= base
    return nums

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]
print(radix_sort([3, 0, 1, 0], base=256))   # [0, 0, 1, 3]

使用基底 256，表示每一回合看一個位元組，所以 32 位元整數只需 4 回合。若要包含負數，可以把負數與非負數分開排序再接起來，或把所有鍵值減去最小值做偏移。對固定長度的字串，則以位置 i 的字元碼作為位數，並從最後一個位置往前處理。

時間與空間複雜度

當 d 是常數（固定寬度的鍵值），且 b 選在接近 n 或固定值（如 256）時，時間為 O(n)。對 n 個互不相同的鍵值，d 至少要有 log_b n，所以對任意大小的鍵值，基數排序並不會勝過 O(n log n)；它之所以快，是因為每一步都是單純的陣列操作。

基數排序與其他排序法的比較

表中 n 是鍵值個數，k 是計數排序的鍵值範圍，d 是位數，b 是基底。只要每一回合的位數排序都是穩定的，LSD 基數排序就是穩定的。它需要結構固定的鍵值，而合併排序、快速排序這類比較式排序可以處理任何排序依據，包括自訂的比較函式。

LSD 與 MSD，以及常見錯誤

何時使用基數排序

基數排序很適合處理大量固定寬度的整數或鍵值，例如 32 位元 ID、時間戳記、IPv4 位址或固定長度字串，尤其是在 GPU 與高效能函式庫中，它規律的記憶體存取很划算。它用於後綴陣列的建構，也用在某些資料庫與圖形運算工作中。對一般的 Python 串列，sorted() 在實務上幾乎總是更快，因為它跑的是最佳化過的 C 程式碼。面試中，被問到如何以線性時間排序時會提到基數排序，例如 Maximum Gap 這道題。