欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

基数排序python实现

程序员文章站 2024-01-05 15:51:58
基数排序python实现 基数排序 基数排序(英语:Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。 所以基数排序的原理就是,先排元素的最后 ......

基数排序python实现

基数排序

基数排序(英语:radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

所以基数排序的原理就是,先排元素的最后一位,再排倒数第二位,直到所有位数都排完。这里并不能先排第一位,那样最后依然是无序。

举个例子:

第一次排最低位,上边的序列变成了下面的样子

基数排序python实现

从这个图中也能看出,排序是基于桶排序实现的。

然后就像排最低位一样,然后再排倒数第二位,再排倒数第三位。注意向桶中放元素的时候一定要按顺序放。

具体代码

这里将列表进行基数排序,默认列表中的元素都是正整数

def radix_sort(s):
    """基数排序"""
    i = 0 # 记录当前正在排拿一位,最低位为1
    max_num = max(s)  # 最大值
    j = len(str(max_num))  # 记录最大值的位数
    while i < j:
        bucket_list =[[] for _ in range(10)] #初始化桶数组
        for x in s:
            bucket_list[int(x / (10**i)) % 10].append(x) # 找到位置放入桶数组
        print(bucket_list)
        s.clear()
        for x in bucket_list:   # 放回原序列
            for y in x:
                s.append(y)
        i += 1

if __name__ == '__main__':
    a = [334,5,67,345,7,345345,99,4,23,78,45,1,3453,23424]
    radix_sort(a)
    print(a)

输出为:

[[], [1], [], [23, 3453], [334, 4, 23424], [5, 345, 345345, 45], [], [67, 7], [78], [99]]
[[1, 4, 5, 7], [], [23, 23424], [334], [345, 345345, 45], [3453], [67], [78], [], [99]]
[[1, 4, 5, 7, 23, 45, 67, 78, 99], [], [], [334, 345, 345345], [23424, 3453], [], [], [], [], []]
[[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345], [], [], [23424, 3453], [], [345345], [], [], [], []]
[[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453], [], [23424], [], [345345], [], [], [], [], []]
[[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453, 23424], [], [], [345345], [], [], [], [], [], []]
[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453, 23424, 345345]

总结

基数排序不仅仅只能排正整数,只要通过调整元素放入桶数组的方式就可以排序字符串,浮点数等