根据基数排序的原理，把自然数从个位开始按位储存到字典树（第四十二课）中，然后按层遍历，就输出排好序的列表了。

　　程序代码（文本代码在附录１)：

　　运行结果：

　　《Python数据结构与算法》到处结束！谢谢您们的关注和陪伴！

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：

Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。

更多课程请打开“学思营”同步网站：

http://www.5xstar.com/doc.html

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社

附录１：

#通用字典式基数排序
#自然数id对象类
class IDData:
     #数据对象构造方法，id排序自然数
     def __init__(self, id):
         self.id = id    
#节点类
class RadixNode:
    def __init__(self):
        self.upRadixes = None  #高位节点
        self.valueList = None  #该节点的排序对象（IDData）列表
#自然数按位字典类
class RadixTree:
    #构造
    def __init__(self, radix=10):
        self.radix = radix  #进位制
        self.root = RadixNode()  #创建根节点，个位父节点
        self.root.upRadixes = [RadixNode() for i in range(radix)]  #创建个位桶
    #添加元素
    def add(self, idData):
        self.__add(self.root, idData.id, idData)  #调用递归方法
    def __add(self, father, id, idData):
        if id < self.radix:  #如果id小于进位制数
            node = father.upRadixes[id]  #该层节点
            if node.valueList == None:  #把对象加入该位列表
                node.valueList = [idData]
            else:
                node.valueList.append(idData)  
        else:  #如果id大于等于进位制数
            curId = id % self.radix  #当层数字
            node = father.upRadixes[curId]  #该层节点       
            if node.upRadixes == None:  #初始化上层
                node.upRadixes = [RadixNode() for i in range(self.radix)]
            id //= self.radix  #进位
            self.__add(node, id, idData)  #递归调用
    #逐层遍历，输出排序列表
    def radixSort(self):
        result = []  #结果表
        lst1 = [self.root]  #当层父节点
        lst2 = []  #当层节点收集器
        while len(lst1)>0:
            for father in lst1:  #遍历当层父节点
                nodes = father.upRadixes  #当层节点
                if nodes != None:  #当层节点不为空
                    for node in nodes:  #遍历当层节点
                        if node.valueList != None:  #如果数据对象列表非空，
                            result.extend(node.valueList)  #加入结果列表
                    lst2.extend(nodes)  #把当层节点加入当层节点收集器
            lst1 = lst2  #上推一层
            lst2 = []
        return result
#自然数组排序
def radixSort(arr, radix=10):
    rTree = RadixTree(radix)  #创建按位排序树
    for a in arr:  #加入元素
        rTree.add(IDData(a))
    rst = rTree.radixSort()  #输出结果
    return [rs.id for rs in rst]
#测试
if __name__ == "__main__":
    arr = [12,3,45,2543,214,1,10,4553,121]
    print(radixSort(arr))