难度：基础。题目原型为洛谷 T708837（私题，题面自定）。本题的考点是按值域分桶的桶排序模板：值域上限提升到 10^6，桶的大小随之变大，但思路仍是「下标 = 数值、一次展开」。

目标

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

• 写出按值域分桶的桶排序模板；
• 判断「值域多大时」计数桶仍是可接受的做法；
• 用 vector 正确初始化大数组，避免栈溢出。

前置知识

• 11.5 桶排序：按值域把数据分到若干桶，再依次展开；
• 11.4 计数排序：值域较小时的 O(n + 值域) 排序。

题目

读入 n 个整数（值域 0..10^6），用桶排序（按值域分桶）把它们从小到大输出到一行。

输入格式

• 第一行一个整数 n；
• 第二行 n 个整数（都在 0..10^6 之间）。

输出格式

一行 n 个整数，为从小到大排序后的结果，空格分隔。

数据范围

项目	范围
个数 n	1 ≤ n ≤ 10⁵
元素值	0 ≤ 值 ≤ 10⁶

样例

样例输入

5
4 2 4 5 1

样例输出

1 2 4 4 5

样例解释

统计各数值出现次数：1:1, 2:1, 4:2, 5:1，按值域顺序展开即得升序结果。

如何验证

先安装 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-16-bucket-sort-template
pnpm lab:score -- labs/chapter-11/exercise/E-11-16-bucket-sort-template

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

完成清单

• 样例输出与题目一致
• 全部相同、取到边界 0 与 10^6 的情况都通过
• 能说出为什么大桶数组要用 vector 而不是普通局部数组

思考题

1. 值域 0..10^6 的桶数组要开多大？为什么建议用 vector 分配？
2. 如果值域上限再升到 10^9，桶排序还合适吗？你会换成什么算法？

题解

点击查看题解

思路

值域 0..10^6，开长度 1000001 的计数桶数组 cnt，读入每个 x 后 cnt[x]++。输出时按值域顺序扫描，cnt[i] 是多少就把 i 输出多少次。

大数组放在堆上（vector）而不是栈上的局部数组，避免栈溢出。

复杂度分析

• 时间复杂度：O(n + 10^6)；
• 空间复杂度：O(10^6)。