材料分享：《CMSC 351: RadixSort》（基数排序算法简介）

在 PostgreSQL 哈希索引所参考的论文中，有涉及到基数排序的地方，因此我们找到一份对应的参考材料，用以辅助理解。

《CMSC 351: RadixSort》材料下载

同时文章中的代码，我们也做了一定的修改（原文的代码在数字超出一定范围后，会排序失败）：

import random
# This unstable version of counting sort
# sorts by the digit passed to it .
# digit = 1 ,10 ,100 , etc .
def countingsort (A, digit, longest_digit):
    n = len(A)
    # 存储新排序以后的数组
    ANEW = [0] * n
    # 根据最长位数，创建一个对应的临时数组，存储坐标信息
    C = [0] * longest_digit
    # 把每一个数字这轮排序中对应的位提取出来
    for i in range (0, n):
        sdigit = int((A[i]/digit)%10)
        # 统计这个数字的出现次数
        C[sdigit] = C[sdigit] + 1
    for i in range (1, longest_digit):
        # 统计这一位之前应该有多少位数字
        C[i] = C[i] + C[i-1]
    # 自 n-1 开始 递减到 0
    for i in range (n-1, -1, -1):
        sdigit = int((A[i]/digit)%10)
        # 数组自 0 开始
        ANEW[C[sdigit]-1] = A[i]
        # 每放置一个，就 -1
        C[sdigit] = C[sdigit] - 1
    for i in range (0, n):
        A [i] = ANEW[i]

def radixsort(A):
    maxval = max(A)
    longest_dight = 1
    # 统计最长位数
    d = 1
    while d < maxval:
        longest_dight = longest_dight + 1
        d = 10 * d
    # 一层层遍历
    d = 1
    while d < maxval :
        print('\t' + 'Sorting by radix : ' + str ( d ))
        countingsort(A, d, longest_dight)
        print('\t' + '\t' + 'Result : ' + str(A))
        d = 10 * d

# 构建原始数列
A = []
for i in range (0, 20):
    A.append(random.randint(0, 100000000000))

# 开始执行 Radix Sort（基数排序）
print('Raw: ' + str(A) + '\n')
radixsort(A)
print('\n' + 'Result: ' + str(A))