python实现基数排序（桶排序、箱排序）

对序列进行排序：[521, 630, 31, 200, 100, 6150, 210, 0, 128, 100, 19]

1. 基本思想：分配、收集
2. 定义：有若干个桶，将关键字为k的记录放入第k个桶里，然后按序号将非空的连接。
3. 详细步骤：
   1. 创建十个桶，用于存放不同的数据
   2. 进行n次分配收集，n为列表中最大数的位数
   3. 每次分配时，将列表中的数据分别放入10个桶中，
   4. 比如第一次将521这个个位数为1的放入桶1中。630这个个位数为0的放入桶0。31这个个位为1的放入桶1。
   5. 分配完成后进行收集
   6. 重复步骤3

   def digit_total(num):  # 计算一个数的位数 #辅助函数
    total = 0
    if num == 0:
        return 1
   
    while num != 0:
        num = num // 10
        total += 1
    return total
   
   
    def get_digit_number(number, digit):  # 给定数据和分位，获取分位上的数字 #辅助函数
        if digit == 0:
            return 0
        if number < 10 ** (digit - 1):
            return 0
        x = 1
        while digit:
            x = number % 10
            number = number // 10
            digit = digit - 1
        return x
   
   
    def bucket_sort(array): # 主函数
        max_digit = digit_total(max(array))  # 计算数组中最大数的位数
   
        bucket_list = [[] for i in range(10)]  # 创建一个装有10个桶的列表
   
        # 分配收集 max_digit 次
        for digit in range(1, max_digit + 1):
            # 1分配
            for item in array:
                index = get_digit_number(item, digit)  # 获取分位上的数字,digi=1时表示获取个位上的数字
                bucket_list[index].append(item)  # 将数据项存入到下标为index的桶中
   
            # 2收集
            array = []
            for bucket in bucket_list:
                n = len(bucket)
                while n:
                    array.append(bucket.pop(0))  # 将桶中数据收集到数组中
                    n -= 1
   
        return array
   
   
    array = [521, 630, 31, 200, 100, 6150, 210, 0, 128, 100, 19]
    print(bucket_sort(array)) #[0, 19, 31, 100, 100, 128, 200, 210, 521, 630, 6150]