从一道CSP-J真题出发：聊聊贪心排序与计数排序

题源：洛谷 P14357 [CSP-J 2025] 拼数 / number（民间数据）

背景

在算法竞赛和日常刷题中，有一类问题看似是"字符串处理"，本质上却是排序思想的灵活运用。这类问题里，最常被低估、也最容易让人"想复杂"的，就是贪心排序——明明一眼就能看出答案，却总有人想写个通用排序、甚至动规。

2025年CSP-J普及组的第一题《拼数》，就是这类问题的典型代表。很多选手看到"从字符串里挑数字拼最大整数"，第一反应是提取数字→存数组→sort降序→输出。这当然能AC，但如果数据范围再大一点（比如10 6 10^6106甚至10 7 10^7107），通用排序的O ( n log ⁡ n ) O(n\log n)O(nlogn)就会成为瓶颈。而本题的数字只有0 ∼ 9 0 \sim 90∼9十种，用计数排序可以把复杂度压到O ( n ) O(n)O(n)，空间只需常数。

本文将从这道真题出发，系统梳理贪心排序的核心思想，重点讲透计数排序在这类"有限取值范围排序"中的优雅应用，并对比它与通用排序的取舍。

一、为什么贪心排序能把问题变简单？

暴力算法的典型坏处是：对每个可能的排列都枚举一遍，找出最大值。全排列的复杂度是O ( n ! ) O(n!)O(n!)，哪怕只有10个数字也直接爆炸。

贪心排序的核心思想是：利用比较规则的特殊性，直接确定每个位置的"最优选择"，从而避免枚举。

举个例子。假设字符串里提取出的数字是[ 2 , 9 , 0 , 1 , 0 ] [2, 9, 0, 1, 0][2,9,0,1,0]，要拼成最大的五位数。暴力做法会枚举5 ! = 120 5! = 1205!=120种排列，找出最大的92100 9210092100。但注意到：多位整数的比较是从最高位开始的，最高位放9 99一定比放2 22优，第二位放2 22一定比放1 11优……以此类推。于是直接从大到小排序即可，无需枚举任何排列。

这就是贪心排序的魔法：不是魔法，是局部最优即全局最优。在"拼最大数"这个问题里，每个位置独立地选择当前可用的最大数字，最终结果就是全局最大。

二、两种实现路径：通用排序 vs 计数排序

在动手写代码之前，先建立一张决策表。几乎所有"从有限集合中选取元素构造最优序列"的问题，都能归到下面两种实现。

1. 通用排序（基于比较的排序）

把数字提取出来，存入数组或字符串，调用std::sort并指定降序比较器。这是最直接、最不容易写错的做法。

特征：

• 代码量少，逻辑直观；
• 时间复杂度O ( n log ⁡ n ) O(n\log n)O(nlogn)，由比较排序的下界决定；
• 适用于任意可比较的元素类型，通用性强；
• 数据量n ≤ 10 6 n \leq 10^6n≤106时完全够用。

2. 计数排序（非比较排序）

由于数字只有0 ∼ 9 0 \sim 90∼9共10种取值，用一个大小为10的数组统计每个数字出现次数，然后从9 99到0 00依次输出即可。

特征：

• 时间复杂度O ( n ) O(n)O(n)，线性扫描即可完成；
• 空间复杂度O ( 1 ) O(1)O(1)（固定大小为10的计数数组）；
• 仅适用于取值范围很小且已知的场景；
• 是"桶排序"的最简形态，也是基数排序的基石。

三、计数排序：从直觉到可复用模板

3.1 计数排序到底在干什么？

把字符串想象成一条传送带，我们用一个"十格篮子"（cnt[0..9]）来统计每种数字出现了几次。right不断把新字符"扔进篮子"：如果是数字，对应格子加一；如果是字母，直接跳过。统计完成后，从篮子第9格倒着往回取，取几个就输出几个——这就是最大的排列。

计数排序特别适合两类问题：

1. 元素取值范围极小
   例如：数字0 ∼ 9 0 \sim 90∼9、字母a ∼ z a \sim za∼z、成绩0 ∼ 100 0 \sim 1000∼100等。

2. 需要稳定排序且数据量大
   例如：10 7 10^7107级别的整数排序，用计数排序或基数排序远快于快速排序。

这两类题表面不同，骨架几乎一样：统计频次 → 按序输出 → 构造结果。

3.2 万能模板

伪代码如下：

初始化 cnt[0..9] = 0 读取字符串 s for 每个字符 c in s: if c 是数字: cnt[c - '0'] += 1 for i 从 9 递减到 0: while cnt[i] > 0: 输出 i cnt[i] -= 1

注意：最内层的while可以换成for j in range(cnt[i])，也可以直接用字符串乘法str(i) * cnt[i]拼接。核心思想不变：按值从大到小，按频次重复输出。

下面用C++写出更贴近实战的骨架：

#include<bits/stdc++.h>usingnamespacestd;intcnt[15];// 计数数组，cnt[i] 记录数字 i 出现的次数string s;intmain(){cin>>s;// 遍历字符串，统计数字频次for(inti=0;i<s.size();i++){if(s[i]>='0'&&s[i]<='9'){cnt[s[i]-'0']++;}}// 从 9 到 0 依次输出for(inti=9;i>=0;i--){while(cnt[i]>0){cout<<i;cnt[i]--;}}cout<<endl;return0;}

模板的价值不在于"复制粘贴就能AC"，而在于把思考路径固定下来：我先统计，再按序输出，注意力可以集中在"如何过滤非数字字符"和"输出格式"两处真正的差异上。刷题时最怕的是边写边想，逻辑乱跳；有了模板，代码结构清晰，调试也更快。

3.3 例题：《拼数》的计数排序实现

题目：给定字符串s ss，仅含小写字母和数字，且至少含一个1 ∼ 9 1 \sim 91∼9的数字。从中选取任意多个数字（每个字符只能用一次），按任意顺序拼成一个正整数，求能拼成的最大值。

思路：窗口内维护数字出现次数。遍历字符串时，数字字符对应格子加一；非数字字符直接跳过。统计完成后，从9 99到0 00依次输出每个数字的所有出现。

#include<bits/stdc++.h>usingnamespacestd;intcnt[15];// 计数数组，记录每个数字（0-9）出现的次数string s;intmain(){cin>>s;// 统计每个数字出现的次数for(inti=0;i<s.size();i++){// 将字符转换为数字索引，并增加对应计数if(s[i]>='0'&&s[i]<='9'){cnt[s[i]-'0']++;}}// 从大到小输出数字（9到0）for(inti=9;i>=0;i--){// 如果当前数字出现过if(cnt[i]!=0){// 输出该数字的所有出现次数while(cnt[i]>0){cout<<i;// 输出当前数字cnt[i]--;// 减少计数}}}// 输出换行符cout<<endl;return0;}

复杂度：每个字符最多被访问一次（统计时），每个数字最多被输出一次（输出时），时间O ( ∣ s ∣ ) O(|s|)O(∣s∣)，空间O ( 1 ) O(1)O(1)（固定大小为10的数组）。

关键细节：if (s[i] >= '0' && s[i] <= '9')的判断必须加。虽然题目保证至少有一个数字，但字符串中混有字母，不加判断会导致cnt数组越界或产生垃圾数据。

3.4 通用排序实现（对比版）

如果你更习惯用std::sort，代码可以这样写：

#include<bits/stdc++.h>usingnamespacestd;string s,ans;intmain(){cin>>s;// 提取所有数字字符for(charc:s){if(c>='0'&&c<='9'){ans+=c;}}// 降序排序sort(ans.begin(),ans.end(),greater<char>());cout<<ans<<endl;return0;}

和计数排序的差异在哪里？这里把"排序"交给了通用算法，时间复杂度是O ( n log ⁡ n ) O(n\log n)O(nlogn)。对于10 6 10^6106的数据量，两种方法都能通过；但如果数据量达到10 7 10^7107或更高，计数排序的线性优势就会显现。

3.5 计数排序的「变体清单」

把常见变体记成清单，刷题时可以秒匹配：

固定长度窗口其实是计数排序的退化：取值范围就是窗口大小，每个值出现0次或1次。

3.6 什么时候不能用计数排序？

记住这句话：计数排序依赖"取值范围很小且已知"。

• 元素是任意整数（如− 10 9 ∼ 10 9 -10^9 \sim 10^9−109∼109）——范围太大，数组开不下。
• 元素是浮点数——无法直接作为数组下标。
• 需要按自定义规则排序（如按字符串长度）——计数排序只能按"值"排序。
• 需要排序的对象是结构体，且按多个字段排序——要用稳定排序或自定义比较器。

面试时若被追问"为什么O ( n ) O(n)O(n)"，就答：数字种类只有10种，统计频次是线性扫描，输出也是线性扫描，整体两趟遍历。

四、贪心排序的底层逻辑：为什么降序就是最大？

4.1 字典序与高位优先

多位整数的比较规则是字典序：从最高位开始逐位比较，第一位大的数整体更大，与位数和后续位无关。

例如：910>899，因为第一位9 > 8 9 > 89>8，后面不管怎么排都不影响结果。因此，把最大的可用数字放在最高位，是局部最优；而每一位都局部最优，就构成了全局最优。

4.2 正整数的隐含约束

题目要求输出"正整数"，且保证至少有一个1 ∼ 9 1 \sim 91∼9的数字。这意味着：

• 不会出现全零的情况：至少有一个非零数字，且非零数字会排在零前面。
• 不会出现前导零问题：因为是从9 99到0 00输出，零总是在最后。
• 位数越多越好：所有数字都用上，位数最长，且高位尽可能大。

这些约束让贪心策略毫无后顾之忧：不需要考虑"要不要跳过某些数字"，全部用上就是最优。

4.3 与"拼接最大数"问题的对比

有一类经典问题：给定若干数字字符串（如["9", "34", "3"]），拼接成最大的数。这时候不能简单降序，因为"34"和"3"的排序规则是"343"vs"334"，需要自定义比较器（a+b > b+a）。

但本题每个"数字"都是单个字符，不存在多位数字的拼接歧义，所以纯降序即可。这是本题比经典题更简单的地方，也是很多选手一眼看穿的原因。

五、通用排序 vs 计数排序：怎么选题？

可以用下面这张决策表快速分流：

1. 元素取值范围很小（如数字、字母、小范围整数）且已知？
   → 优先想计数排序，O ( n ) O(n)O(n)线性复杂度。

2. 元素取值范围大或未知，或需要自定义比较规则？
   → 使用std::sort等通用排序，O ( n log ⁡ n ) O(n\log n)O(nlogn)。

3. 数据量n ≤ 10 5 n \leq 10^5n≤105，且代码正确性优先于性能？
   → 两种都可以，选自己写得最顺手的。

4. 数据量n ≥ 10 7 n \geq 10^7n≥107，且元素是整数或字符串？
   → 考虑基数排序（字符串）或计数排序（整数），避免O ( n log ⁡ n ) O(n\log n)O(nlogn)的常数开销。

实际做题时，先分类再写模板，比一上来敲sort省很多时间。面试官也更喜欢你先说出"为什么选这种排序"，再落代码。

六、工程视角：不止刷题

计数排序和贪心思想不只是竞赛技巧，工程里同样常见：

• 日志级别统计：ERROR、WARN、INFO、DEBUG 只有四种，用计数数组统计各类日志条数，O ( n ) O(n)O(n)完成。
• 字符频率分析：文本处理中统计字母出现次数，用于哈夫曼编码或简单加密分析。
• 数据去重与压缩：已知取值范围时，用位图（Bitmap）或计数数组替代哈希表，内存更省。
• 基数排序的底层：大数据排序框架中，基数排序的多轮计数排序是核心模块。

刷题时建立的"按取值范围选择算法"的习惯，迁移到写业务代码时，往往体现为更少的不必要开销和更干净的数据流。

七、小结

贪心排序的本质，是利用比较规则的特殊性，直接构造最优解，避免枚举。

计数排序 = 非比较排序 + 频统计计。先扫描统计，再按序输出，时间O ( n ) O(n)O(n)，空间O ( k ) O(k)O(k)（k kk为取值范围大小）。
通用排序 = 基于比较。代码简洁，通用性强，时间O ( n log ⁡ n ) O(n\log n)O(nlogn)，适用于任意可比较元素。
贪心策略 = 局部最优即全局最优。在"拼最大数"问题中，高位放最大数字就是最优解的充要条件。

回到《拼数》这道题，它教会我们的不只是"怎么写对"，更是"怎么选对"：当数据范围极小且已知时，不要惯性思维地写sort，计数排序才是更优雅、更高效的答案。

本文代码已在洛谷 P14357 上通过测试。如有错误或补充，欢迎在评论区留言交流。