基数排序

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)

扫描关注, 与我技术互动

QQ交流群: 211426309

加入知识星球, 每天收获更多精彩内容

分享日常研究的python技术和遇到的问题及解决方案