[数据结构与算法]算法设计与分析——排序算法（九）：基数排序

分类目录：《算法设计与分析》总目录
相关文章：
· 排序算法（一）：插入排序
· 排序算法（二）：归并排序
· 排序算法（三）：堆排序
· 排序算法（四）：选择排序
· 排序算法（五）：冒泡排序
· 排序算法（六）：希尔排序
· 排序算法（七）：快速排序
\qquad · ①基础知识
\qquad · ②快速排序的性能
\qquad · ③快速排序的随机化
\qquad · ④快速排序的分析
· 排序算法（八）：计数排序
· 排序算法（九）：基数排序
· 排序算法（十）：桶排序
· 排序算法：比较排序算法的下界
· 排序算法：十大排序算法总结

基数排序是一种用在卡片排序机上的算法，现在你只能在博物馆找到这种卡片排序机了。博物馆中的一张卡片有80列，在每一列上机器可以选择在12个位置中的任一处穿孔。通过机械操作，我们可以对排序机“编程”来检查每个卡片中的给定列，然后根据穿孔的位置将它们分别放人12个容器中。操作员就可以逐个容器地来收集卡片，其中第一个位置穿孔的卡片在最上面，其次是第二个位置穿孔的卡片，依此类推。

对十进制数字来说，每列只会用到10个位置（另两个位置用于编码非数值字符）。一个$d$位数将占用$d$列。因为卡片排序机一次只能查看一列，所以要对$n$张卡片上的$d$位数进行排序，就需要设计一个排序算法。

从直观上来看，你可能会觉得应该按最高有效位进行排序，然后对得到的每个容器递归地进行排序，最后再把所有结果合并起来。遗憾的是，为了排序一个容器中的卡片，10个容器中的9个都必须先放在一边。这一过程产生了许多要保存的临时卡片。与人们直观感受相悖的是，基数排序是先按最低有效位进行排序来解决卡片排序问题的。然后算法将所有卡片合并成一叠，其中0号容器中的卡片都在1号容器中的卡片之前，而1号容器中的卡片又在2号容器中的卡片前面，依此类推。之后，用同样的方法按次低有效位对所有的卡片进行排序，并把排好的卡片再次合并成一叠。重复这一过程，直到对所有的$d$位数字都进行了排序。此时，所有卡片已按$d$位数完全排好序。所以，对这一叠卡片的排序仅需要进行$d$轮。下图说明了一叠7张3位数卡片的基数排序过程：

为了确保基数排序的正确性，一位数排序算法必须是稳定的。卡片排序机所执行的排序是稳定的，但操作员必须确保卡片从容器中被取出时不改变顺序，即使一个容器中的所有卡片在该位都是相同的数字也要确保这一点。

在一台典型的串行随机存取计算机上，我们有时会用基数排序来对具有多关键字域的记录进行排序。例如，我们希望用三个关键字（年、月和日）来对日期进行排序。对这个问题，我们可以使用基于特殊比较函数的排序算法：给定两个日期，先比较年，如果相同，再比较月，如果还是相同，就比较日。我们也可以采用另一种方法，用一种稳定排序算法对这些信息进行三次排序：先日，再月，最后是年。

基数排序的代码是非常直观的。在下面的代码中，我们假设$n$个$d$位的元素存放在数组$A$中，其中第1位是最低位，第$d$位是最高位。在下面的代码中d=len(str(max_num)):

def radix_sort(arr):
    d = len(str(max(arr)))
    for k in range(d):
        bucket_list=[[] for i in range(10)]
        for i in arr:
            bucket_list[i//(10**k)%10].append(i)
        arr=[j for i in bucket_list for j in i]
    return arr

最后，我们用动图演示一下基数排序的全过程：