难度：基础。题目原型为洛谷 T216135（私题，题面自定）。本题的考点是桶排序最朴素的形式：值域只有 0..1000，直接拿计数数组当桶，「下标 = 数值」，一次扫描完成排序。

目标

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

• 手写「桶 = 计数数组」的桶排序；
• 解释为什么这种写法只适合值域不大且是整数的数据；
• 说明桶排序与计数排序在这一情形下的等价关系。

前置知识

• 11.1 排序的基本概念；
• 11.5 桶排序：把数据按值域分到若干「桶」，再对每个桶排序或直接展开。

题目

读入 n 个 0..1000 之间的整数，用桶排序（桶 = 计数）把它们从小到大输出到一行。

输入格式

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

输出格式

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

数据范围

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

样例

样例输入

10
8 5 5 3 2 9 7 3 5 0

样例输出

0 2 3 3 5 5 5 7 8 9

样例解释

统计各数值出现次数：0:1, 2:1, 3:2, 5:3, 7:1, 8:1, 9:1，按 0..1000 顺序展开即得升序结果。

如何验证

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

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

完成清单

• 样例输出与题目一致
• 全部相同、取到边界 0 与 1000 的情况都通过
• 能说出「cnt[x]++」里下标 x 代表什么

思考题

1. 如果值域变成 0..10^9，还能直接开这么大的计数数组吗？为什么？
2. 桶排序和计数排序的边界在哪里？什么情况下它们其实是一回事？

题解

点击查看题解

思路

开长度 1001 的计数数组 cnt，读入每个 x 后 cnt[x]++。输出时按 0..1000 顺序扫描，cnt[i] 是多少就把 i 输出多少次。因为下标本身就是升序，展开后就是有序结果。

复杂度分析

• 时间复杂度：O(n + 1000)；
• 空间复杂度：O(1000)。