题目原型为洛谷 P1271 [深基 9.例 1] 选举学生会。本题的考点是计数排序（非比较排序）：票的编号值域很小且已知，用「编号本身」当下标即可线性时间完成排序。

目标

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

• 说出计数排序的适用前提：值域小且已知；
• 用「编号当下标」的数组计数实现零比较的排序；
• 解释计数排序为什么能突破比较排序的 Ω(n log n) 下界。

前置知识

• 11.4 计数排序的原理与复杂度分析；
• 数组下标与值域的对应关系。

题目

学校正在选举学生会成员，有 n 个投票人，m 个候选人。每位投票人投一张票，票上写着被投候选人的编号（1 到 m）。请按编号从小到大，把所有有效票的编号依次输出。

输入格式

• 第一行两个整数 n 和 m；
• 第二行 n 个整数，表示每张票上的候选人编号。

输出格式

一行 n 个整数，为所有票的编号从小到大排列的结果，相邻两个整数用空格分隔。

数据范围

项目	范围
投票人数 n	1 ≤ n ≤ 1000
候选人人数 m	1 ≤ m ≤ 999
票上编号	1 ≤ 编号 ≤ m

样例

样例输入

10 5
2 5 1 3 5 1 2 5 4 1

样例输出

1 1 1 2 2 3 4 5 5 5

样例解释

统计每个编号出现次数：1 出现 3 次，2 出现 2 次，3 出现 1 次，4 出现 1 次，5 出现 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-01-counting-votes
pnpm lab:score -- labs/chapter-11/exercise/E-11-01-counting-votes

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

完成清单

• 样例输出与题目一致
• 值域上限 m=999、全部同票、单张票三种边界通过
• 能说出「计数排序何时优于快排、何时不能用」

思考题

1. 如果编号范围变成 1 ≤ 编号 ≤ 10⁹，还能用计数排序吗？为什么？
2. 计数排序是稳定排序吗？如果把计数数组改成「前缀和 + 逆序填充」，稳定性会怎样？

题解

点击查看题解

思路

开一个 cnt[m+1] 的计数数组，读入每张票时 cnt[编号]++；然后按编号 1..m 的顺序，把每个编号输出 cnt[i] 次。整个过程一次比较都不用做。

复杂度分析

• 时间复杂度：O(n + m)；
• 空间复杂度：O(m)（计数数组）。