基數排序法又稱桶子法（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些"桶"中，藉以達到排序的作用，基數排序法是屬于穩定性的排序，其時間復雜度為O (nlog(r)m)，其中r為所采取的基數，而m為堆數，在某些時候，基數排序法的效率高于其它的比較性排序法。

代碼如下:
# -*- coding: utf-8 -*-

def _counting_sort(A, i):
    """計數排序，以i位進行排序，以適用于基數排序。
    Args:
        A (Sequence): 排序數組
        i (int): 位數，從0開始而不是1
    """
    C = [0] * 10 # 任意位值范圍為[0,9]
    A = [(a / (10 ** i) % 10, a) for a in A] # 元素i位值及其自身的元組的數組
    for k, a in A:
        C[k] = C[k] + 1
    for i in xrange(1, 10):
        C[i] = C[i] + C[i-1]
    B = [0] * len(A) # 結果數組
    for k, a in A[::-1]:
        B[C[k]-1] = a
        C[k] = C[k] - 1
    return B

def radix_sort(A, d):
    """基數排序，從最低位進行排序直到最高位：
    RADIX-SORT(A, d)
    1  for i ← 1 to d
    2    do use a stable sort to sort array A on digit i

    Args:
        A (Sequence): 排序數組
        d (int): 最大數位數
    """
    for i in xrange(d): # 遍歷位數，從低到高
        A = _counting_sort(A, i)
    return A

def rsort(A, d):
    """基數排序（桶排序版本）"""
    for i in xrange(d): # 遍歷位數，從低到高
        S = [[] for _ in xrange(10)] # 存放[0,9]位數值所對應元素（[0-9]10個桶）
        for a in A: # 遍歷元素
            S[a / (10 ** i) % 10].append(a) # 存放對應位數值的元素（元素當前位值在哪個桶就放進去）
        A = [a for b in S for a in b] # 以當前位數值排序好的A（依次從各桶里把元素拿出來）
    return A

if __name__ == '__main__':
    import random, timeit

    items = range(10000)
    random.shuffle(items)

    def test_sorted():
        print(items)