美文网首页排序算法(python)
python实现基数排序(Radix Sort)

python实现基数排序(Radix Sort)

作者: 阿旭123 | 来源:发表于2020-12-09 12:05 被阅读0次

python实现【基数排序】(Radix Sort)

算法原理及介绍

基数排序核心思想是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。

算法过程描述

  1. 取得数组中的最大数,并取得位数;

  2. arr为原始数组,从最低位开始取每个位组成radix数组;

  3. 对radix进行计数排序(利用计数排序适用于小范围数的特点);

算法排序图解如下

基数排序.gif

python实现代码

def radixSort(arr):
    n = len(str(max(arr)))  # 记录最大值的位数
    for k in range(n):#n轮排序
        # 每一轮生成10个列表
        bucket_list=[[] for i in range(10)]#因为每一位数字都是0~9,故建立10个桶
        for i in arr:
            # 按第k位放入到桶中
            bucket_list[i//(10**k)%10].append(i)
        # 按当前桶的顺序重排列表
        arr=[j for i in bucket_list for j in i]
    return arr

如果喜欢作者,欢迎点赞、收藏及关注,谢谢!
点击下面相应的链接即可查看各个算法的详细介绍及python实现方法

  1. 冒泡排序(BubbleSort)
  2. 选择排序(SelectionSort)
  3. 插入排序(InsertSort)
  4. 归并排序(MergeSort)
  5. 快速排序(QuickSort)
  6. 堆排序(Heap Sort)
  7. 计数排序(Count Sort)
  8. 桶排序(Bucket Sort)
  9. 基数排序(Radix Sort)
  10. 希尔排序(Shell Sort)

相关文章

网友评论

    本文标题:python实现基数排序(Radix Sort)

    本文链接:https://www.haomeiwen.com/subject/muhhgktx.html