面试必备算法｜图解基数排序（Python）

基数排序

基数排序的思想

​ 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从个位开始依次进行排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

图解基数排序

​ 进行基数排序的时候我们按照从低位到高位排序即可，直到最高位排序完成。

基数排序的代码实现

# 基数排序
lst = list(map(int, input().split(',')))


def RadixSort(alist):
    i = 0
    n = 1
    max_num = max(alist)
    while max_num >= 10**n:
        n += 1
    while i < n:
        bucket = {}
        for x in range(10):
            bucket.setdefault(x, [])
        for x in alist:
            radix = int((x / (10**i)) % 10)
            bucket[radix].append(x)
        j = 0
        for k in range(10):
            if len(bucket[k]) != 0:
                for y in bucket[k]:
                    alist[j] = y
                    j += 1
        i += 1
    return alist


RadixSort(lst)