萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Python 實作基數排序演算法

基數排序 是非比較式整數排序演算法,透過「個位數→十位數→百位數...」依位數分桶排序,時間複雜度 O(k·n) (k 為最大位數)。本文提供純 Python 實作,適合教學與中小規模資料排序。

程式碼實作

from random import randint

def radix_sort(arr, max_digits=8):
    """LSD 基數排序 (最低位優先),基數 10"""
    for k in range(max_digits):
        # 10 個桶子 (0-9)
        buckets = [[] for _ in range(10)]
        divisor = 10 ** k
        
        for num in arr:
            digit = (num // divisor) % 10
            buckets[digit].append(num)
        
        # 扁平化桶子順序回原陣列
        arr = [num for bucket in buckets for num in bucket]
    return arr

def main():
    # 產生 9999 個 1~99,999,999 隨機整數
    data = [randint(1, 99_999_999) for _ in range(9999)]
    sorted_data = radix_sort(data)
    
    # 驗證前 20 筆
    print(sorted_data[:20])

if __name__ == "__main__":
    main()

演算法解析

  1. 位數迴圈:從最低位 (k=0) 到最高位 (k=max_digits-1)。
  2. 分桶:依當前位數值 (0-9) 將元素放入對應桶子,保持桶內相對順序 (穩定排序關鍵)。
  3. 收集:按桶子順序 0→9 串接元素,形成新陣列供下一輪使用。

適用場景與限制

  • ✅ 非負整數、固定位數範圍 (如身分證字號、固定長度代碼)。
  • ✅ 資料量大且位數較小時極快 (O(n))。
  • ❌ 負數需額外處理 (分正負兩組或偏移)。
  • ❌ 浮點數、字串需轉換為定長整數表示。
  • ❌ 位數過大 (k 大) 時空間/時間優勢消失,不如 Timsort (Python 內建 sorted)。

效能比較參考

對 10 萬筆 8 位數隨機整數:

  • 基數排序 (純 Python) 約 0.3 秒
  • 內建 sorted() 約 0.02 秒 (C 實作,高度優化)

實務上除非有特殊需求 (如嵌入式環境無標準庫、教學展示),優先使用內建 sorted() 或 list.sort()。

copyright © 萬盛學電腦網 all rights reserved