基数排序
基本思想：
- 基数排序(Radix Sort)是桶排序的扩展，将整数按位数切割成不同的数字，然后按每个位数分别进行了多轮的桶排序。具体实现：从低位开始将待排序的数按照这一位的值放到相应的编号为0~9的桶中。等到低位排完得到一个子序列，再将这个序列按照次低位的大小进入相应的桶中，一直排到最高位为止，数组排序完成。
- 待排序的序列中的值必须是整数而且范围跨度不应太大，否则排序开销太大。例如可以用于学生成绩的排序，因为成绩的范围仅在100以内。
时间复杂度：
- 对于 n 个数值，执行一次分配和收集的时间为O(n）。如果关键字有 d 位，如果关键字有 d 位，则要执行 d 遍。 所以总的运算时间为 O(d*n)。可见不同的基数 r 所用时间是不同的。当 r 或 d 较小时，这种算法较为节省时间。上面讨论的是顺序表的基数排序，这个算法同样也是用与链式的记录排序，只是要求额外附加一下队列的头、尾指针。
基数排序时一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。按照关键字先后顺序，基数排序可以分为高位优先法和低位优先法。
一般来说低位优先法要比高位简单。因为高位优先是分治法思想，对子集按相同方法排序，是一个递归的过程。而低位优先法只要通过x次分配收集操作就可以完成排序，x是取决于关键字的多少
'''
Creat by HuangDandan
2018-08-19
dandanhuang@sjtu.edu.cn
基数排序
基本思想：将整数按位数切割成不同的数字，然后按每个位数分别比较。
步骤：
1-将整数按位数切割成不同的数字，然后按每个位数分别比较。从低位开始将待排序的数按照这一位的值放到相应的编号为0~9的桶中。
2-等到低位排完得到一个子序列，再将这个序列按照次低位的大小进入相应的桶中，一直排到最高位为止，数组排序完成。
编程实现注意点：
0-简单获取列表中最大数值的位数
1-如何按照位数将列表中的数值放入桶中
2-如何依次进行从个位数、十位数、百位数等的操作
将每次放入桶中的值拿出赋给原先的列表
'''
def RadixSort(Lst):
d = len(str(max(Lst))) #列表中的最大元素的位数
for i in range(d): #0-9一共10个桶
BucketLst = [[] for k in range(10)]
for j in range(len(Lst)):
BucketLst[Lst[j]//(10**i)%10].append(Lst[j]) #10**i是关注意点，之前一直是10**d，debug才发现
Lst = [number for B in BucketLst for number in B] #关键2-依次拿出桶中的元素，给原列表Lst,
# 而不是给缓存 temp = [number for B in BucketLst for number in B]
return Lst
if __name__ == "__main__":
Lst1 = [1,44,5,222,1]
print(Lst1)
print(RadixSort(Lst1))
#print('------------------------------------')
温故知新：
我在编写程序的时候，没有传入序列中最大值的位数d，而是通过调用python里面内置的函数进行计算，d = len(str(max(Lst))) ，这样本身就会增加程序的时间复杂度。python内置函数求解max(Lst)，需要对列表中的所有元素进行遍历，考虑时间复杂度，可以传入d参数~~
参考博客：
https://www.jb51.net/article/123676.htm
https://blog.csdn.net/will130/article/details/45196575
http://www.dwtmy.com/Aboutus.asp?title=%C1%AA%CF%B5%CE%D2%C3%C7
https://www.jianshu.com/p/8f8f19d7b2b9
https://www.cnblogs.com/surgewong/p/3381646.html
