乐趣区

python实现十大排序算法之基数排序Radix-Sort

简介

基数排序 (Radix Sort) 是一种非比较型整数排序算法,是桶排序的扩展。基本思想是:将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。按照低位先排序,分别放入 10 个队列中,然后采用先进先出的原则进行收集;再按照高位排序,然后再收集;依次类推,直到最高位,最终得到排好序的数列。对于数值偏小的一组序列,其速度是非常快的,时间复杂度达到了线性,而且思想也非常的巧妙。

算法实现步骤

  1. 取得数组中的最大数,并取得位数;
  2. 对数位较短的数前面补零;
  3. 分配,先从个位开始,根据位值 (0-9) 分别放到 0~9 号桶中;
  4. 收集,再将放置在 0~9 号桶中的数据按顺序放到数组中;
  5. 重复 3~4 过程,直到最高位,即可完成排序。

Python 代码实现

# radix_sort 代码实现

from typing import List

def radix_sort(arr:List[int]):
    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
# 测试数据

if __name__ == '__main__':
    import random
    random.seed(54)
    arr = [random.randint(0,100) for _ in range(10)]
    print("原始数据:", arr)
    arr_new = radix_sort(arr)
    print("计数排序结果为:", arr_new)
# 输出结果

原始数据:[17, 56, 71, 38, 61, 62, 48, 28, 57, 42]
计数排序结果为:[17, 28, 38, 42, 48, 56, 57, 61, 62, 71]

动画演示

算法分析

  • 时间复杂度

    设待排序的数组 $R\left[1,2,\cdots,n\right]$,数组中最大的数是 $k$ 位数,基数为 $r$(十进制基数为 10,数字 0~9,最多需要 10 个桶来映射数组元素)。处理一位数,需要将数组元素映射到 $r$ 个桶中,映射完成后还需要收集,相当于遍历整个数组,则遍历一位数的时间复杂度为 $O(n+r)$。所以,总的时间复杂度为 $O((n+r)×k)$。

  • 空间复杂度

    基数排序过程中,需要开辟 $r$ 个队列,最坏条件下可能用到一个 $r×n$ 的二维数组来做为桶,所以空间复杂度为 $O(r×n)$。

  • 稳定性

    基数排序过程是分别排序和收集,不影响相等元素的相对位置,所以是稳定的。

  • 综合评价

    时间复杂度(平均) 时间复杂度(最好) 时间复杂度(最坏) 空间复杂度 排序方式 稳定性
    $O((n+r)×k)$ $O((n+r)×k)$ $O((n+r)×k)$ $O(r×n)$ out-place 稳定

联系我们

个人博客网站:http://www.bling2.cn/

Github 地址:https://github.com/lb971216008/Use-Python-to-Achieve

知乎专栏:https://zhuanlan.zhihu.com/Use-Python-to-Achieve

小专栏:https://xiaozhuanlan.com/Use-Python-to-Achieve

博客园:https://www.cnblogs.com/Use-Python-to-Achieve

退出移动版