基数排序（Radix Sort）

# /*
# 基数排序（Radix Sort）
# --------------------------------------------------------
# 原理：
# 按“位数”逐位排序的线性时间排序算法。
# 典型方式为 LSD（从最低位开始排），
# 通过对每一位进行稳定排序，最终得到整体有序序列。
#
# 基数排序常应用于整数、大量定长数据的排序任务。
# */

# 获取最大值的位数
def max_digits(arr):
    if not arr:
        return 0
    return len(str(max(arr)))


# 基数排序（LSD 方式）
def radix_sort(arr):
    if len(arr) <= 1:
        return arr

    max_len = max_digits(arr)    # 取得最高位数

    exp = 1                      # 从个位开始
    result = arr[:]

    for _ in range(max_len):
        # 使用 10 个桶：0-9
        buckets = [[] for _ in range(10)]

        # 将元素按当前位放入桶中
        for num in result:
            digit = (num // exp) % 10
            buckets[digit].append(num)

        # 合并桶内容
        result = []
        for b in buckets:
            result.extend(b)

        exp *= 10    # 进入下一位

    return result


# 示例演示
data = [170, 45, 75, 90, 802, 24, 2, 66]
print("排序前：", data)
result = radix_sort(data)
print("排序后：", result)

# --------------------------------------------------------
# 关键要点总结：
# 1) 按位排序：从最低位到最高位逐层处理；
# 2) 使用稳定排序（通常是桶分配）作为核心步骤；
# 3) 时间复杂度 O(k·n)，k 为最大位数，n 为元素数量；
# 4) 空间复杂度 O(n + k)，需要多个桶；
# 5) 在整数、大规模、位数固定的场景中表现优异；
# 6) 非比较排序，适合结构规整的数字集。
# */
#
# 排序前： [170, 45, 75, 90, 802, 24, 2, 66]
# 排序后： [2, 24, 45, 66, 75, 90, 170, 802]