Python 排序算法：基数排序

zltzlt

Python 排序算法：基数排序

基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为 O(kn)，为数组长度，k 为数组中的数的最大的位数；

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。

最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

基数排序基于分别排序，分别收集，所以是稳定的。

动图演示

                               
登录/注册后可看大图

代码

1. def radix_sort(a):
   
2.     i = 0  # 初始为个位排序
   
3.     n = 1  # 最小的位数置为1（包含0）
   
4.     max_num = max(a)  # 得到带排序数组中最大数
   
5.     while max_num > 10 ** n:  # 得到最大数是几位数
   
6.         n += 1
   
7.     while i < n:
   
8.         bucket = {}  # 用字典构建桶
   
9.         for x in range(10):
   
10.             bucket.setdefault(x, [])  # 将每个桶置空
    
11.         for x in a:  # 对每一位进行排序
    
12.             radix = int((x / (10 ** i)) % 10)  # 得到每位的基数
    
13.             bucket[radix].append(x)  # 将对应的数组元素加入到相应位基数的桶中
    
14.         j = 0
    
15.         for k in range(10):
    
16.             if len(bucket[k]):       # 若桶不为空
    
17.                 for y in bucket[k]:  # 将该桶中每个元素
    
18.                     a[j] = y  # 放回到数组中
    
19.                     j += 1
    
20.         i += 1
    
21. 
    
22. 
    
23. nums = [5, 18, 10, 3, 2, 9]
    
24. print(f"原数组：{nums}")
    
25. radix_sort(nums)
    
26. print(f"排序后数组：{nums}")

复制代码