排序算法之基数排序 红太狼 2021-10-19 14:50 302阅读 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
还没有评论,来说两句吧...