Python 排序算法：基数排序
Python 排序算法：基数排序基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为 O(kn)，为数组长度，k 为数组中的数的最大的位数；
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。
最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
基数排序基于分别排序，分别收集，所以是稳定的。
动图演示
https://s1.ax1x.com/2020/03/22/8IRay8.gif
代码
def radix_sort(a):
i = 0# 初始为个位排序
n = 1# 最小的位数置为1（包含0）
max_num = max(a)# 得到带排序数组中最大数
while max_num > 10 ** n:# 得到最大数是几位数
n += 1
while i < n:
bucket = {}# 用字典构建桶
for x in range(10):
bucket.setdefault(x, [])# 将每个桶置空
for x in a:# 对每一位进行排序
radix = int((x / (10 ** i)) % 10)# 得到每位的基数
bucket.append(x)# 将对应的数组元素加入到相应位基数的桶中
j = 0
for k in range(10):
if len(bucket): # 若桶不为空
for y in bucket:# 将该桶中每个元素
a = y# 放回到数组中
j += 1
i += 1
nums =
print(f"原数组：{nums}")
radix_sort(nums)
print(f"排序后数组：{nums}")
页:
[1]