基数排序

1. 基数排序

直接使用维基百科里的定义：

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列

乍一看，似乎还是没有思路，那我们就一点一点的来理解

2. 一个正整数有多少位？

一个正整数有几位呢？你以为这是一个很傻的问题，好，请用程序来回答

方法一，转成str，求len

print(len(str(98372)))

方法二，log

import math
print(int(math.ceil(math.log(98372, 10))))

log(98372, 10) 的值是小于5的，而ceil返回的是上入整数，这样，也可以获得整数的位数

3. 从低位到高位输出一个正整数的每一位

a = 98372
index = 1
while True:
    b = a%(10**index)
    c = b//(10**(index-1))
    if c == 0 and b == a:
        break
    print(c)
    index += 1

都是基本的对数字进行操作的算法，%是求模，/是进行除运算，什么时候break呢，c等于0且b等于a的时候，这个时候，index等于6，而a的位数只有5位

4. 算法推理过程

有了2，3做铺垫，我们可以开始理解基数排序了，假设有一个序列 lst = [3,56,1,24,134,67,356,321] 它是无序的

那么我们分配10个桶，编号从0到9，现在，请将个位数字是0的放在0号桶里，个位数字是1的放在1号桶里，以此类推，最后，这10个桶里的情况是下面的样子

[[], [1, 321], [], [3], [24, 134], [], [56, 356], [67], [], []]

我们按照从小到大的顺序从桶里把数字都取出来，是这个样子，我们叫它序列 A

[1, 321, 3, 24, 134, 56, 356, 67]

虽然还是无序的，但是，你仔细看，如果只看个位数，是不是已经变得有序了呢？1 1 3 4 6 6 7

接下来，我们再分配10个桶，编号从0到9，对于序列A，将十位数字是0的放在0号桶里，十位数字是1的放在1号桶里，以此类推，如果一个数字没有十位，那就是0呗，最后，桶里的情况是这样的

[[1, 3], [], [321, 24], [134], [], [56, 356], [67], [], [], []]

现在，把这些数字都取出来，我们叫它序列B

[1, 3, 321, 24, 134, 56, 356, 67]

依然是一个无序序列，但是，只看个位是有序的，只看十位也是有序的

最后，再分配10个桶，编号从0到9，对于序列B，将百位数字是0的放在0号桶里，百位数字是1的放在1号桶里，以此类推，如果没有百位，那就是0，最后，桶里的情况是这样的

[[1, 3, 24, 56, 67], [134], [], [321, 356], [], [], [], [], [], []]

把这些数都取出来，结果如下

[1, 3, 24, 56, 67, 134, 321, 356]

一个无序的序列，经过一轮轮排序，个位变得有序，在此基础上，十位变得有序，在此基础上百位变得有序。。。。。最后，整个序列都变得有序了

5. 示例代码

import math
def sort(a, radix=10):
    """a为整数列表， radix为基数"""
    K = int(math.ceil(math.log(max(a), radix))) # 最大值有几位数
    bucket = [[] for i in range(radix)] # 不能用 [[]]*radix
    for i in range(1, K+1): # K次循环
        for val in a:
            bucket[val%(radix**i)//(radix**(i-1))].append(val) # 取整数第K位数字 （从低到高）
        del a[:]
        for each in bucket:
            a.extend(each) # 桶合并
        bucket = [[] for i in range(radix)]

lst = [3,56,1,24,134,67,356,321]
sort(lst)
print(lst)

13.8 基数排序