难度：进阶。题目原型为洛谷 U104252 基数排序模板（私题，题面自定）。本题的考点是 LSD 基数排序：不比较元素大小，而是按十进制位从低位到高位逐位做稳定排序，每轮借助计数排序在 O(n+k) 内完成。

目标

完成本题后，你应该能够：

• 说出基数排序为什么必须用稳定排序处理每一位；
• 独立写出「计数排序 + 按位循环」的 LSD 基数排序模板；
• 说明时间复杂度 O(d(n+k)) 中 d、k 各是什么。

前置知识

• 计数排序（对整数范围的稳定排序）；
• 十进制数位提取：(x / exp) % 10。

题目

读入 n 个非负整数，用基数排序把它们从小到大输出。

输入格式

• 第一行一个整数 n；
• 第二行 n 个非负整数，以空格分隔。

输出格式

一行 n 个从小到大排好序的整数，以空格分隔。

数据范围

项目	范围
整数个数 n	1 ≤ n ≤ 10⁵
元素值	0 ≤ a[i] ≤ 10⁹

样例

样例输入

6
329 457 657 839 436 720

样例输出

329 436 457 657 720 839

样例解释

LSD 基数排序从个位开始，依次按十位、百位……做稳定计数排序。上面的数据只需 3 轮（个位、十位、百位）即可排好。

如何验证

先安装 Node.js、pnpm 和支持 C++17 的编译器。

# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample
make interactive
make score

Windows 没有安装 Make 时，在仓库根目录使用等价的 pnpm 入口：

pnpm lab:run -- labs/chapter-11/exercise/E-11-17-radix-sort-template
pnpm lab:score -- labs/chapter-11/exercise/E-11-17-radix-sort-template

标准输出参与判题，调试信息请写入标准错误。

完成清单

• 样例输出与题目一致
• 含 0、个位数、多位数、最大值 10⁹ 的情况都通过
• 能说出「每轮必须稳定」的原因

思考题

1. 如果把每轮的计数排序换成不稳定的排序，结果会错在哪里？举一个反例。
2. 处理的轮数 d 由什么决定？为什么值域 10⁹ 最多需要 10 轮？
3. 基数排序适合什么场景？什么时候反而不如 std::sort 的 O(n log n)？

题解

点击查看题解

思路

按十进制位从低位到高位（LSD）逐位处理。每一轮：

1. 用计数排序按当前位 (x / exp) % 10（0～9）把整个数组稳定排序；
2. exp 乘 10 进入下一位，直到 maxValue / exp == 0 为止。

计数排序保证「当前位相同的元素保持上一轮已排好的相对顺序」，于是逐位逼近最终有序结果。稳定性的实现要点：前缀和后，从后往前遍历原数组放置到临时数组。

复杂度分析

• 时间复杂度：O(d(n + k))，其中 d 为最大数的十进制位数（≤ 10），k = 10；
• 空间复杂度：O(n + k)。