Python 基數排序 實現與效能分析

基數排序 是非比較型整數排序算法，時間複雜度 O(d·(n+k)) (d=位數, n=元素數, k=基數)，適合大量整數排序。本文展示 Python 純實現、效能基準測試、與內建 sorted() 比較、適用場景與優化方向。

核心原理：LSD (最低位優先)

1. 找出最大值決定最大位數 d。
2. 從個位 (10^0) 到最高位，依序執行穩定計數排序。
3. 每輪將元素按當前位數字 (0-9) 分桶，再按順序合併。

純 Python 實現

def radix_sort(arr: list[int]) -> list[int]:
    """基數排序 (LSD)，原地修改並回傳列表"""
    if not arr:
        return arr
    
    # 1. 找最大值決定輪數
    max_val = max(arr)
    exp = 1  # 10^0, 10^1, ...
    
    # 2. 處理負數：分離負數與非負數，負數取絕對值排序後反轉
    neg = [x for x in arr if x < 0]
    non_neg = [x for x in arr if x >= 0]
    
    def _radix_sort_non_neg(nums):
        if not nums:
            return nums
        max_num = max(nums)
        exp = 1
        while max_num // exp > 0:
            buckets = [[] for _ in range(10)]
            for num in nums:
                digit = (num // exp) % 10
                buckets[digit].append(num)
            # 合併桶
            nums[:] = [num for bucket in buckets for num in bucket]
            exp *= 10
        return nums
    
    sorted_neg = _radix_sort_non_neg([-x for x in neg])[::-1]  # 反轉並加負號
    sorted_neg = [-x for x in sorted_neg]
    sorted_non_neg = _radix_sort_non_neg(non_neg)
    
    arr[:] = sorted_neg + sorted_non_neg
    return arr

簡潔版 (僅非負整數，教學用)

def radix_sort_simple(arr):
    """假設所有元素 >= 0"""
    if not arr:
        return arr
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        buckets = [[] for _ in range(10)]
        for num in arr:
            buckets[(num // exp) % 10].append(num)
        arr[:] = [num for bucket in buckets for num in bucket]
        exp *= 10
    return arr

效能基準測試

import random, time

def benchmark():
    sizes = [10_000, 100_000, 1_000_000]
    for n in sizes:
        data = [random.randint(0, 10**9) for _ in range(n)]
        
        # Python 內建 Timsort
        t0 = time.perf_counter()
        sorted_builtin = sorted(data)
        t1 = time.perf_counter()
        print(f"n={n:,}  sorted(): {(t1-t0)*1000:.1f} ms")
        
        # 基數排序
        data_copy = data[:]
        t0 = time.perf_counter()
        radix_sort_simple(data_copy)
        t1 = time.perf_counter()
        print(f"n={n:,}  radix_sort: {(t1-t0)*1000:.1f} ms")
        assert data_copy == sorted_builtin
        print()

if __name__ == '__main__':
    benchmark()

典型輸出 (Intel i7, Python 3.11)

n=10,000   sorted(): 2.1 ms
n=10,000   radix_sort: 8.5 ms

n=100,000  sorted(): 24.3 ms
n=100,000  radix_sort: 82.7 ms

n=1,000,000 sorted(): 285 ms
n=1,000,000 radix_sort: 920 ms

效能分析：為何 Python 純實現慢於內建？

加速方案：NumPy / Numba / C 擴充

# 方案 1: NumPy 向量化 (需資料轉 ndarray)
import numpy as np
def radix_sort_numpy(arr):
    a = np.array(arr, dtype=np.int64)
    max_val = a.max()
    exp = 1
    while max_val // exp > 0:
        # 計數排序向量化
        digits = (a // exp) % 10
        # argsort 穩定排序
        a = a[np.argsort(digits, kind='stable')]
        exp *= 10
    return a.tolist()

# 方案 2: Numba JIT 編譯
from numba import jit
@jit(nopython=True)
def radix_sort_numba(arr):
    n = len(arr)
    max_val = arr.max()
    exp = 1
    output = np.empty(n, dtype=np.int64)
    while max_val // exp > 0:
        count = np.zeros(10, dtype=np.int64)
        for i in range(n):
            count[(arr[i] // exp) % 10] += 1
        for i in range(1, 10):
            count[i] += count[i-1]
        for i in range(n-1, -1, -1):
            d = (arr[i] // exp) % 10
            count[d] -= 1
            output[count[d]] = arr[i]
        arr[:] = output[:]
        exp *= 10
    return arr

適用場景與選擇建議

常見誤區

• 以為基數排序在 Python 總是最快：純 Python 迴圈開銷極大，僅在 C/Numba/硬體加速下才具優勢。
• 忽略負數處理：標準 LSD 僅處理非負整數，負數需分離或偏移。
• 空間複雜度：需 O(n+k) 額外空間 (桶 + 輸出陣列)，非原地演算法。
• 穩定性：計數排序若從後向前填充輸出陣列則穩定；Python 列表推導式合併桶天然穩定。

基數排序是理解「非比較排序」的經典範例，但在 Python 實務中，**優先使用內建 sorted()**；極大規模整數排序才考慮 NumPy/Numba 加速版本。