共计 1477 个字符，预计需要花费 4 分钟才能阅读完成。
简介
基数排序 (Radix Sort) 是一种非比较型整数排序算法，是桶排序的扩展。基本思想是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。按照低位先排序，分别放入 10 个队列中，然后采用先进先出的原则进行收集；再按照高位排序，然后再收集；依次类推，直到最高位，最终得到排好序的数列。对于数值偏小的一组序列，其速度是非常快的，时间复杂度达到了线性，而且思想也非常的巧妙。
算法实现步骤
- 取得数组中的最大数，并取得位数；
- 对数位较短的数前面补零；
- 分配，先从个位开始，根据位值 (0-9) 分别放到 0~9 号桶中;
- 收集，再将放置在 0~9 号桶中的数据按顺序放到数组中;
- 重复 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
