Python 排序算法：基数排序

zltzlt

Python 排序算法：基数排序

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

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

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

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

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

动图演示

                               
登录/注册后可看大图

代码

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[radix].append(x)  # 将对应的数组元素加入到相应位基数的桶中
        j = 0
        for k in range(10):
            if len(bucket[k]):       # 若桶不为空
                for y in bucket[k]:  # 将该桶中每个元素
                    a[j] = y  # 放回到数组中
                    j += 1
        i += 1


nums = [5, 18, 10, 3, 2, 9]
print(f"原数组：{nums}")
radix_sort(nums)
print(f"排序后数组：{nums}")