基數排序 是非比較式整數排序演算法,透過「個位數→十位數→百位數...」依位數分桶排序,時間複雜度 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()
sorted)。對 10 萬筆 8 位數隨機整數:
sorted() 約 0.02 秒 (C 實作,高度優化)實務上除非有特殊需求 (如嵌入式環境無標準庫、教學展示),優先使用內建 sorted() 或 list.sort()。