# 基数排序又称桶子法，是桶排序的扩展，用于排序数字或者字母类型的数据。
# 1. 将所有待排序整数（注意，必须是非负整数）统一为位数相同的整数，位数较少的前面补零。
#   一般用10进制，也可以用16进制甚至2进制。所以前提是能够找到最大值，得到最长的位数，设 k 进制下最长为位数为 d 。
# 2. 从最低位开始，依次进行一次稳定排序。这样从最低位一直到最高位排序完成以后，整个序列就变成了一个有序序列。

# 举个例子，有一个整数序列，0, 123, 45, 386, 106，下面是排序过程：
#       第一次排序，个位，000 123 045 386 106，无任何变化
#       第二次排序，十位，000 106 123 045 386
#       第三次排序，百位，000 045 106 123 386
#       最终结果，0, 45, 106, 123, 386, 排序完成。

# 首先，基数排序和计数排序都可以看作是桶排序。
# 计数排序本质上是一种特殊的桶排序，当桶的个数取最大( maxV-minV+1 )的时候，就变成了计数排序。

# 基数排序也是一种桶排序。桶排序是按值区间划分桶，基数排序是按数位来划分；
# 基数排序可以看做是多轮桶排序，每个数位上都进行一轮桶排序。

# 当用最大值作为基数时，基数排序就退化成了计数排序。
# 当使用2进制时，k=2最小，位数d最大，时间复杂度O(nd)会变大，空间复杂度O(n+k)会变小。
# 当用最大值作为基数时，k=maxV最大，d=1 最小，此时时间复杂度O(nd)变小，
# 但是空间复杂度O(n+k)会急剧增大，此时基数排序退化成了计数排序。

# 基数排序在进制k和位数d之间折中，在空间复杂度和时间复杂度之间进行折中。


def radix_sort(s):
    """基数排序"""
    i = 0  # 记录当前正在排那一位，最低位为1
    max_num = max(s)  # 最大值
    j = len(str(max_num))  # 记录最大值的位数
    while i < j:
        bucket_list = [[] for _ in range(10)]  # 初始化桶数组
        for x in s:
            bucket_list[int(x / (10 ** i)) % 10].append(x)  # 找到位置放入桶数组
        print(bucket_list)
        s.clear()
        for x in bucket_list:  # 放回原序列
            for y in x:
                s.append(y)
        i += 1


if __name__ == '__main__':
    a = [334, 5, 67, 345, 7, 345345, 99, 4, 23, 78, 45, 1, 3453, 23424]
    radix_sort(a)
    print(a)
