排序算法之基数排序

红太狼 2021-10-19 14:50 361阅读 0赞

一、原理

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

步骤：

（1）创建10个桶（列表）分别给每一个数位

（2）遍历每个数位

（3）遍历列表中的每个元素，并将它放到相应的桶中

（4）将元素恢复至列表中

![1137363-20190630164620130-1587301180.gif][]

二、实现

import random
    
    
    def list_to_bucket(li, i):
        bins = [[] for i in range(10)]  # 创建10个桶（列表）分别给每一个数位
        for num in li:
            j = num // (10**i) % 10  
            bins[j].append(num)
        return bins
    
    
    def bucket_to_list(bins):
        return [i for bin in bins for i in bin]
    
    
    def radixSort(li):
        max_num = max(li)
        i = 0
        while 10 ** i <= max_num:  # 循环每一次就比较每一个数的每一位
            bins = list_to_bucket(li, i)
            li = bucket_to_list(bins)
            i += 1
        return li
    
    
    li = [random.randint(0, 200) for i in range(10000)]
    radixSort(li)
    print(radixSort(li))

参考：

[https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/10.radixSort.md][https_github.com_hustcc_JS-Sorting-Algorithm_blob_master_10.radixSort.md]

[https://visualgo.net/zh/sorting][https_visualgo.net_zh_sorting]

转载于:https://www.cnblogs.com/shenjianping/p/11110316.html

[1137363-20190630164620130-1587301180.gif]: /images/20211019/aac826e86a75436abdc4d5a6667918d7.png
[https_github.com_hustcc_JS-Sorting-Algorithm_blob_master_10.radixSort.md]: https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/10.radixSort.md
[https_visualgo.net_zh_sorting]: https://visualgo.net/zh/sorting