企业官网建设流程全解析

两百万张选票堆在桌上，候选人编号最大也就到一千，你要在有限的时间里把它们按编号从头排到尾——这不是什么脑筋急转弯，就是 P1271《选举学生会》的原样描述。这道题摆在基础教材排序章节的第一个例题位置上，很多人两分钟就交完了，觉得它简单得没什么可讲。但恰恰是它，把“比较排序”和“计数排序”这两条完全不同的技术路线摆在了同一个场景里，逼你第一次做出算法选型上的判断。我见过太多人刷完几十道排序题，脑子里仍然只有 sort 一个选项，遇到“值域很小、数据量很大”的场景第一反应还是 sort 一遍了事。这篇我按自己刷题和带人踩坑的经历，把这道题从读题、选型、写代码、调超时到延伸扩展整个链条拆开讲一遍，适合刚学完数组和循环、正准备接触排序的新手，也适合想回头把基础夯实的同学。

1. 从题意到数据规模：这道题在暗示你用什么算法

1.1 把题面翻译成一句数据结构的话

题目描述不复杂：有 n 名候选人，编号从 1 到 n；收集到 m 张选票，每张票上写着某个候选人的编号；要求把这些编号从小到大排好，按顺序输出。输入第一行是两个整数 n 和 m，第二行是 m 个整数，每个整数的取值范围在 1 到 n 之间。输出就是一行，里面是 m 个升序排列的整数。

把它翻译成数据结构语言，其实就一句话：给定一个长度为 m 的整数序列，值域被限制在 [1, n] 这个很小的闭区间内，要求升序输出。注意这句话里有两个要素，一个是序列长度 m，一个是值域上界 n，后面所有的算法选型都是围绕这两个数字的大小关系做文章。很多同学读题只记“要排序”，把值域这一条限制当成废话跳过去，其实这才是出题人给的最大的提示。同样一道题，如果值域是任意 32 位整数，它就是另一道题了。

还有一种常见的误读方式，就是把输出理解成“每个候选人的得票数”。这道题要的是把选票序列排好，而不是让你输出一张统计表。不过有个细节值得说：当你用计数排序做完之后，手上那份额外数组cnt[1..n]里装的恰好就是每个候选人的得票数，只要你把最后那个“回放”循环改成逐个打印cnt[i]，输出就立刻变成得票统计。也就是说，这道题的解法天然覆盖了“排序”和“统计”两种需求，这个认知在后面的延伸部分还会用到。

1.2 数据规模里藏着出题人的亲笔提示

看数据范围是整个解题流程里最容易被跳过、也最不该跳过的一步。题面给出的界限大致是：候选人数 n 不超过一千这个量级，选票数 m 却能达到两百万。换算一下比例，m 是 n 的两千倍左右。

这个比例关系非常关键。它意味着整个序列里一定会出现大量重复：两百万张票分给一千个候选人，平均每个人两千票。重复率高到这种程度，任何以“比较任意两个元素”为核心的排序算法都会做大量无用功，因为它们不得不反复去比较那些其实完全相同的值。而计数排序的思路正好相反：我不关心第几张票和第几张票谁大谁小，我只关心编号 v 出现了几次，出现一次就在cnt[v]上加一。值域小不是限制，是礼物，它让你可以用下标直接定位。

我在给新人讲这道题的时候，习惯让他们先回答一个问题：如果 m 变成几百万、n 变成十亿，这道题还能这么做吗？答案是不能，需要用完全不同的方法。反过来，如果 m 只有一百、n 有一百万，那也没必要计数排序，直接 sort 更省事。算法选型永远是一个关于数据规模的判断，而不是关于算法本身高低的判断，这句话在这道题上体现得淋漓尽致。

1.3 比较排序在这里到底亏在哪

先别急着否定std::sort。诚实地说，两百万个 int 用std::sort排一遍，在一台普通的开发机上也就一两百毫秒，多数题目的时限是 1 秒，它是能过的。所以这道题并不是“sort 会超时”，而是“sort 在这里性价比明显不划算”。

从理论上看，基于比较的排序算法下界是 O(m log m)。m 取两百万，log₂(m) 大约是 21，也就是四千万次以上的比较操作，每一次比较还伴随着指针跳转和元素交换。而计数排序的复杂度是 O(n + m)，在这道题里就是两百万加一千，量级上差了一个数量级都不止。实际跑起来，两者的差距会被缓存局部性进一步放大：计数排序的访问模式是顺序扫一遍输入、顺序扫一遍值域，几乎全是缓存友好的；而std::sort用的是内省排序，递归划分加上随机访问，指针到处跳。

我在一台用了好几年的笔记本上做过粗略对比，两百万随机票数下，std::sort加常规输出大概一百五十毫秒量级，计数排序加手写输出能压到几十毫秒。这个差距在平时刷题不算什么，但你要知道它的来源，等到数据量再翻十倍、或者时限收紧到两百毫秒的时候，这个选择就变成生死问题了。学算法不怕暂时用不上，怕的是不知道还有别的路。

2. 计数排序的核心机制：用下标替你做记忆

2.1 一个教室分座位的类比

要理解计数排序，我通常用一个场景打比方：假设有一千个座位的教室，座位号从 1 到 1000，每个学生手里有一张纸条，上面写着他的座位号。现在要让所有人按座位号从前往后排好队，最笨的办法是两两比较、反复交换，这就是比较排序的思路。

而计数排序做的是另一件事：它准备一个有一千个格子的登记板，学生只要走到登记板前，在自己座位号对应的格子里画一笔就走，画完就回座位。所有人都画完之后，你从 1 号格子开始往右走，每个格子里有几笔，就念几遍这个格子号，念出来的顺序天然就是升序。整个过程里，没有任何两个人被拿出来比较过，排序的信息完全由“下标”这个天然的位置结构承担了。

对应到代码上，这个登记板就是一个整型数组，下标就是候选人编号，数组里存的值就是“画了几笔”。这种方法成立的前提是值域有限，因为你要实实在在地准备出这么多个格子；值域一旦大到无法开数组，这个方法就崩了。所以计数排序是典型的“用空间和值域换时间”的算法，它不是万能的，但在合适的地方是最优的。

2.2 一趟扫描加一趟回放，复杂度怎么算才不糊弄

计数排序的流程可以精确拆成三步。第一步，把cnt数组全部初始化为 0，这一步代价是 O(n)。第二步，顺着输入读 m 个数，每读到一个 x，就把cnt[x]加一，代价是 O(m)。第三步，从 1 到 n 遍历cnt，对每个下标 v，把 v 打印cnt[v]次，代价同样是 O(n + m)，因为总共打印了 m 个数。

三步加起来是 O(n + m)，额外空间是一个长度为 n 的计数数组，也就是 O(n)。这个复杂度表达式要注意一点：它不是 O(m)，因为它跟值域上限也有关。假如值域 n 也到了两百万这个量级，那 O(n + m) 就退化成跟 m 同阶了，优势就没那么明显。这就是为什么判断适不适合用计数排序，要看 n 和 m 的比值，而不是只看 m 有多大。

还有个细节容易被忽略：第三步打印的时候，每个数字打印几次，取决于cnt[v]的具体值。写循环时如果写成for (int k = 0; k <= cnt[v]; ++k)，就会多打一个，属于典型的差一错误。我建议初学阶段习惯写成k < cnt[v]，比k <= cnt[v] - 1更不容易看错，因为cnt[v]是闭区间的右端点，写法上与自己数数的方式一致。这种小习惯看着无所谓，但在考场上紧张的时候，能省下不少 debug 时间。

2.3 什么情况下计数排序会当场失灵

第一种情况，值域过大。如果候选人编号不是 1 到 1000，而是 1 到 10 亿，那cnt数组根本开不出来，内存直接爆掉。这种时候要么换回比较排序，要么用基数排序按位拆分，后文会展开讲。

第二种情况，排序对象的键不只是整数。比如你要按某个浮点分数排序，或者按字符串排序，那“下标即键值”这个前提就不成立了，计数排序无从下手。它的适用范围严格限制在以较小的非负整数为排序键的场景。

第三种情况，需要稳定性而你没有保持住。计数排序本身是可以写成稳定的：从后往前遍历原序列，把元素放到前缀和确定的位置上。但在这道题里，我们只关心输出值本身，输出的全是相同的数字，稳定性完全用不上。这一点值得单独强调，因为很多人在学完计数排序后，会误以为凡是计数排序都必须实现前缀和加稳定放置那一套，其实那套是为基数排序做准备的，单次计数排序不必那么复杂。

3. 从能跑到跑得快：完整实现与实测

3.1 C++ 基础版：先跑通再谈优化

我建议任何人第一次做这道题，都用最朴素的写法跑通一遍，不要一上来就抄快读模板。朴素版长这样：

#include <cstdio> const int MAXN = 1005; int cnt[MAXN]; int main() { int n, m, x; scanf("%d%d", &n, &m); for (int i = 0; i < m; ++i) { scanf("%d", &x); ++cnt[x]; } for (int v = 1; v <= n; ++v) { for (int k = 0; k < cnt[v]; ++k) { printf("%d ", v); } } return 0; }

这段代码每一行都有讲究。MAXN取 1005 而不是 1000，是因为候选人编号最大就是 n，数组下标要用到 n，多留五个位置是防止边界写错时越界踩到别的数据。这个“多开五格”的习惯我从学 C 语言起就保留至今，它救过我至少十次。

下标从 1 开始用，而不是从 0 开始，是因为候选人的编号定义就是从 1 开始的。如果你强行改成从 0 开始，输入的时候要减一、输出的时候要加一，多出来两次运算不说，还特别容易在某个地方漏掉。让数据结构的下标语义和题目的业务语义对齐，是一个能显著降低出错率的习惯，代价只是多占一个元素的空间。

用scanf而不是cin，是因为在默认配置下cin和 C 的输入输出流是同步的，每次读写都要走一层额外的机制，两百万次输入累积起来的开销相当可观。这不是什么玄学，是实打实的函数调用开销。

3.2 输入输出才是这两百万数据的真正瓶颈

很多人以为这道题的难点在排序，其实跑一遍就知道，计算部分（那两百万次++cnt[x]）几乎不花时间，真正的耗时全在输入和输出上。两百万个整数，每个最多四位数字加一个分隔符，输入流里就是接近十兆字节的字符，输出也是同样规模。

输入侧的第一层优化是关掉流同步：在main开头加ios::sync_with_stdio(false);和cin.tie(nullptr);，然后用cin读。这一招能让cin的速度接近scanf，代码可读性还更好。第二层优化是换scanf。第三层才轮到手写快读，用fread一次性把整块输入读进内存缓冲区，然后自己用指针扫描解析数字。

输出侧同理。最坑的是cout << x << endl，endl除了换行还会强制刷新缓冲区，两百万次刷新是灾难级的。哪怕只把endl换成'\n'，速度也能提升几倍。想再快就自己攒一个字符缓冲区，把所有输出拼好之后一次性fwrite出去。

下面这份是追求极限的版本，把输入输出都做成了手动缓冲：

#include <cstdio> const int MAXN = 1005; int cnt[MAXN]; static char ibuf[1 << 24], obuf[1 << 24]; int main() { int len = (int)fread(ibuf, 1, sizeof(ibuf) - 1, stdin); ibuf[len] = '\0'; int p = 0; int n = 0, m = 0; while (ibuf[p] < '0' || ibuf[p] > '9') ++p; while (ibuf[p] >= '0' && ibuf[p] <= '9') n = n * 10 + (ibuf[p++] - '0'); while (ibuf[p] < '0' || ibuf[p] > '9') ++p; while (ibuf[p] >= '0' && ibuf[p] <= '9') m = m * 10 + (ibuf[p++] - '0'); for (int i = 0; i < m; ++i) { while (ibuf[p] < '0' || ibuf[p] > '9') ++p; int x = 0; while (ibuf[p] >= '0' && ibuf[p] <= '9') x = x * 10 + (ibuf[p++] - '0'); ++cnt[x]; } int q = 0; for (int v = 1; v <= n; ++v) { for (int k = 0; k < cnt[v]; ++k) { char tmp[8]; int tl = 0, t = v; while (t) { tmp[tl++] = (char)('0' + t % 10); t /= 10; } while (tl) obuf[q++] = tmp[--tl]; obuf[q++] = ' '; } } fwrite(obuf, 1, q, stdout); return 0; }

缓冲区大小是1 << 24，也就是十六兆字节。为什么要这么大？两百万个四位数，加上分隔符，大约是十兆字节的数据量，开十六兆能一次性兜住。如果你的平台内存限制比较紧，可以改成循环fread，每次读一兆，边读边解析，只是代码会复杂一些。手写输出的部分，把整数转字符是逆序生成的，所以要再用一个循环倒着塞回缓冲区，这个细节忘了就会输出反过来的数字，我第一次写的时候就在这里栽过。

3.3 Python 版本与它特有的坑

Python 做这道题，思路完全一样，但要绕开两个大坑：input()逐行读和print逐个输出。

import sys def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) m = int(data[1]) cnt = [0] * (n + 1) for tok in data[2:2 + m]: cnt[int(tok)] += 1 parts = [] for v in range(1, n + 1): c = cnt[v] if c: parts.append((str(v) + ' ') * c) sys.stdout.write(''.join(parts)) main()

第一个关键点是sys.stdin.buffer.read()，它一次把整个输入读成字节串，然后split()切成词元列表，绕开了逐行读取的解析开销。如果你用for _ in range(m): x = int(input())，两百万次函数调用足够让你等待到怀疑人生。

第二个关键点是输出拼接策略。我没有用parts.append(str(v))循环追加两百万次，而是利用 Python 字符串乘法的特性，(str(v) + ' ') * c一次生成该候选人所有重复的输出片段，然后统一join。这样列表里的元素个数最多只有 n 个（不超过一千），而不是 m 个，大大减轻了内存和垃圾回收压力。这个技巧在 Python 做计数类输出时非常好用，值得记住。

第三个点是cnt数组长度取n + 1，同样是为了让下标可以直接用候选人编号。Python 的列表下标越界会直接抛异常，不会像 C 那样默默读到脏数据，所以调试起来反而更直观。

3.4 各版本粗略耗时对照

下面这张表是我在普通笔记本上反复跑几十次得到的量级感受，不同机器差异很大，只能用来做相对比较，不要当绝对标准：

从表里能看出一个规律：算法复杂度带来的收益是数量级的，而输入输出优化带来的收益是常数倍的，但因为常数因子被放大了两百万次，这个常数倍的收益在实际测试里往往比换算法还明显。先保证复杂度对，再抠常数，这个顺序不能反。

4. 常见问题与排查实录

4.1 本地跑得通、提交就出错的几类情况

第一类，输出末尾多了空格。我的写法每个数字后面都跟一个空格，行末自然也多一个。多数判题系统在比较时会忽略行末空白，但也有少数是严格逐字符比对的，会出现本地和线上结果不一致。稳妥的写法是把最后一个数字单独处理，或者先存到结果数组里再join。

第二类，数组下标越界却没报错。C++ 不会做边界检查，cnt[n + 3]越界写入可能刚好落在别的全局变量上，程序照常运行但结果莫名其妙。这类问题的排查办法是把数组开大十格，如果结果突然正确了，那就是越界。

第三类，变量没初始化。int cnt[1005];写在main里面是栈上的局部数组，内容是不确定的垃圾值；写在函数外面是全局数组，会被零初始化。这道题刚好需要全部清零，所以我把cnt定义成了全局变量，省去了手动清零这一步。如果你习惯写在里面，务必加一行memset(cnt, 0, sizeof(cnt));。

4.2 一份值得收藏的排查速查表

用表格对照排查，比一行一行读代码快得多。我自己遇到问题时，第一反应不是看代码，而是先看“现象是什么”，再到这张表里对号入座，能省掉一大半时间。

4.3 对拍与造数据：验证正确性的可靠办法

再简单的题也可能写错，最稳的验证手段是写一个暴力版本做对拍。这道题的暴力版就是用std::sort直接排，逻辑绝对简单，几乎不可能有错。

// 暴力对照版 std::vector<int> a(m); for (int i = 0; i < m; ++i) scanf("%d", &a[i]); std::sort(a.begin(), a.end()); for (int i = 0; i < m; ++i) printf("%d ", a[i]);

然后写一个小脚本，循环生成随机数据，跑两遍程序，用系统自带的文件比较工具比对输出。生成数据的时候注意让 n 小一点、m 大一点，比如 n 取 10、m 取 1000，这样才能把重复率高的场景覆盖到；同时也要造一批 n 和 m 都比较小的边界数据，比如 m 等于 1、n 等于 1，用来验证边界。

这个对拍流程本身比这道题更有价值。它是我现在写任何涉及数据处理的程序的默认动作：先写一个慢但一定对的版本，再写一个快但可能错的版本，用随机数据反复比对。很多人写算法题靠的是眼睛看代码找 bug，这是效率最低的方式，机器能做的验证就不要用自己的注意力。

5. 这道题还能往外延伸多远

5.1 加个前缀和，从“排序”变成“求名次”

现在换个需求：不是把选票排好输出，而是要求输出每一张选票对应的名次（也就是它排在所有票里的第几位，重复的按规则处理）。这时候光有计数数组就不够了，还需要对它做一次前缀和，求出每个值前面一共有多少个元素。

int pre[MAXN], sum = 0; for (int v = 1; v <= n; ++v) { pre[v] = sum; sum += cnt[v]; }

pre[v]表示“编号小于 v 的票一共有多少张”，那么编号 v 的票占据的位置区间就是[pre[v], pre[v] + cnt[v] - 1]。这个技巧是基数排序的核心步骤，也是很多统计类题目的通用套路。它的思想很简单：先把分布算出来，再用累计和把分布转换成位置。我第一次真正理解前缀和的价值，就是在这道题的延伸里，而不是在那些抽象的模板题里。

5.2 值域爆炸时怎么办：从单趟到多趟

如果候选人编号不是一千以内，而是十亿以内，一次开数组显然不可能。这时候的思路是把这个大值域按位拆成若干段，每段都小到可以开数组，然后跑多趟计数排序。这种做法的典型代表是基数排序：先按最低若干位排一遍，再按次高若干位排一遍，每趟都保持稳定性，最终整体有序。

这条路线自然引出稳定性的重要性。单趟计数排序用不用稳定无所谓，因为输出的值都一样；但多趟叠加时，第二趟必须保持第一趟内部的相对顺序，否则前一趟白做了。这也说明为什么很多教材在讲计数排序时一定要讲到“从后往前遍历原数组”这个细节——那是为了维持稳定，为后面组合成基数排序做准备。

5.3 这种“用下标当索引”的思路在工程里的身影

抛开竞赛，计数的思路在日常开发中到处都是。统计一个接口在一天内每分钟的调用次数，值域是 1440，用一个长度 1440 的数组按下标累加，比用哈希表去查来查去快得多。统计一段文本里每个字符出现的次数，值域是 256 或者字符集的规模，也是同样的套路。这些东西看起来平淡无奇，但当你处理千万级数据时，选数组还是选哈希表，性能差距是肉眼可见的。

我个人的判断标准很简单：如果键是较小的非负整数，数组永远优先于哈希容器。这条经验在写高频统计逻辑时屡试不爽，包括计数排序在内的很多“小技巧”，本质上都是这条原则的具体应用。而这道 P1271 选举学生会，恰好是理解这条原则最省力的入口。

最后分享一个我做这类题时的习惯：代码写完之后，先在脑子里跑一遍最小的边界，比如 n 等于 1、m 等于 1 的时候输出对不对；再跑一遍最极端的，比如所有票都投给同一个人的时候，内层循环会不会把输出撑爆。这两次心算花不了二十秒，但能拦下八成以上的低级错误。至于这道题本身，后续还可以把它改成多组数据、改成带权重的票数、改成需要输出稳定顺序的版本，每改一次，你对计数这个基础动作的理解就深一层。