基数排序的python实现

基数排序

基数排序是一种非比较型排序算法，其原理是将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序，这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

算法步骤

1. 找出待排序的数组中最大数，并取得这个数的位数；
2. 计算出位数；
3. 按照位数排序；
4. 合并；
5. 返回结果；
6. 重复步骤2~5直到所有位数排序完成。

CODE

def cardinality_sort(arr: List) -> List:
    if len(arr) <= 1:
        return arr
    max_val = max(arr)
    bucket = [[] for _ in range(10)]
    arr = [str(x) for x in arr]
    max_len = len(str(max_val))
    arr = [x.zfill(max_len) for x in arr]
    for i in range(max_len - 1, -1, -1):
        for x in arr:
            bucket[int(x[i])].append(x)
        arr = [item for sublist in bucket for item in sublist]
        bucket = [[] for _ in range(10)]
    return [int(x) for x in arr]