信息奥赛课课通C第154页第1题标题叫近似排序。我第一次看到这四个字时第一反应是按与某个目标值的接近程度排序直到把题面读完才反应过来它其实是在处理一件很朴素的事把 1 到 N 之间每个整数的十进制数字倒过来写得到一个新的数然后按这个新数从小到大排序。数字短的时候看不出难度一旦牵扯到 10、20 这类末尾带 0 的数排序结果会跟你直觉里的输出完全不一样。这道题非常适合拿来练三样东西数字拆位、排序规则的定制、以及排序稳定性对结果的影响。如果你刚接触 C或者正准备信息学奥赛入门组的比赛这题值得一道一道抠透。1. 先拆题近似到底在说什么考点藏在哪里1.1 最容易被误读的题名很多同学看到近似排序四个字会往近似算法约等于的方向想实际上这道题跟近似没有任何关系。教材里最常见的题面描述是输入一个正整数 N把 1 到 N 的所有整数按倒序数从小到大排序并输出。所谓倒序数就是把一个数的十进制数字顺序完全反过来比如 123 的倒序数是 32110 的倒序数是 1100 的倒序数也是 1。为什么叫近似因为最终的序列跟原数的自然顺序相比像是被倒序数打乱后的近似结果。比如 N20 时1 到 20 对应的倒序数是1 → 12 → 2...9 → 910 → 111 → 1112 → 2113 → 3114 → 4115 → 5116 → 6117 → 7118 → 8119 → 9120 → 2按倒序数从小到大排列原数的输出顺序会变成1 10 2 20 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19看到没有20 会跑到 2 的后面、3 的前面整个序列不再是简单的 1 到 20 顺序输出。这就是近似二字的来源看起来像是排序但排序依据藏在每个数的倒序数里。1.2 数字反转核心拆位操作解决这道题绕不开一个基础函数求一个数的倒序数。C 实现非常短int rev(int x) { int r 0; while (x 0) { r r * 10 x % 10; x / 10; } return r; }这个函数的本质是拆位。以 123 为例123 % 10 3把 3 放入r此时r 3x变成 12。12 % 10 2r 3 * 10 2 32x变成 1。1 % 10 1r 32 * 10 1 321x变成 0循环结束。关键点在于r r * 10 x % 10这一步r * 10相当于把已经拼出来的数字整体往左挪一位腾出个位给当前数的个位。这个过程跟十进制位权的本质完全对应。特别要注意末尾带 0 的数比如 10第一次取余得到 0此时r还是 0x变成 1第二次r 0 * 10 1 1。所以 10 的倒序数是 1而不是 01。这符合整数的自然表示前导 0 不显示。如果题目变了要求保留前导 0比如要求 10 的倒序数是 01 并按字符串处理那就不能只用整数反转得转成字符串再 reverse那是完全不同的解法。1.3 考点梳理这道题虽然放在入门部分但它同时踩中了好几个常考的点数字拆位也就是%10和/10的组合使用自定义排序规则不能直接用默认的sort对整个原数组排序排序稳定性当倒序数相同的时候比如 1 和 10 的倒序数都是 1谁排在前面必须有明确规则对sort函数底层行为的理解很多初学者在这里栽跟头。如果只求把答案跑出来难度不高如果把这些考点全弄明白这道题的价值就远超 p154 这一页了。2. 两种主流做法先算好再排还是边排边算2.1 结构体预处理思路最清晰的做法最常见的解法是定义一个结构体把原数和它的倒序数一起存下来#include iostream #include vector #include algorithm using namespace std; struct Node { int orig; int val; }; int rev(int x) { int r 0; while (x 0) { r r * 10 x % 10; x / 10; } return r; } bool cmp(const Node a, const Node b) { if (a.val ! b.val) return a.val b.val; return a.orig b.orig; } int main() { int n; cin n; vectorNode a; for (int i 1; i n; i) { a.push_back({i, rev(i)}); } sort(a.begin(), a.end(), cmp); for (int i 0; i n; i) { if (i) cout ; cout a[i].orig; } cout endl; return 0; }orig存原来的数val存倒序后的数排序时先比val如果倒序数相同再比orig。这样写至少有三个好处第一每个数只调用一次rev。排序过程中比较器只是简单比较两个整数比较代价很小。第二逻辑清楚。结构体把原始数据和排序依据绑定在一起后面不管怎么排都不会搞混谁是谁。第三方便扩展。如果题目要求额外输出倒序数、或者要求按倒序数相同时按输入顺序输出只需在结构体里再加一个字段或者在cmp里调整规则。2.2 Lambda 实时计算代码最短但要谨慎另一种写法是直接用sort加 lambda在比较器里现场计算倒序数#include iostream #include vector #include algorithm using namespace std; int rev(int x) { int r 0; while (x 0) { r r * 10 x % 10; x / 10; } return r; } int main() { int n; cin n; vectorint a; for (int i 1; i n; i) a.push_back(i); sort(a.begin(), a.end(), [](int x, int y) { int rx rev(x), ry rev(y); if (rx ! ry) return rx ry; return x y; }); for (int i 0; i n; i) { if (i) cout ; cout a[i]; } cout endl; return 0; }这段代码看起来简洁很多不需要结构体直接对原数数组排序。但代价是排序过程中每次比较都要把两个数的倒序数重新算一遍。sort的平均比较次数是 O(N log N)也就是说rev会被调用 O(N log N) 次。如果 N 只有几百几千完全没问题但如果 N 到 10^6 级别重复计算带来的常数开销就会变得明显。2.3 数据量不同选型思路不一样对比维度结构体预处理Lambda 实时计算代码量稍多短小精悍rev 调用次数每个数只算一次每次比较算两次大 N 性能更稳可能变慢可读性字段清晰适合新手依赖对 lambda 的掌握出错风险低容易忘记处理相等情况我个人建议初学阶段两种都要会。结构体是竞赛里最通用的写法因为大部分排序题到最后都可以抽象成每个元素带着几个关键字段按某个字段排序的模型lambda 写法在刷小数据量题目、写测试代码时很省事但不要成为唯一的选择。3. 完整实现与手动验证从写代码到确认结果3.1 一套可以直接交的干净代码把前面的内容拼起来整理成一份我实际会提交的版本#include iostream #include vector #include algorithm using namespace std; struct Item { int num; int rnum; }; int reverseNum(int x) { int res 0; while (x 0) { res res * 10 x % 10; x / 10; } return res; } bool cmp(const Item a, const Item b) { if (a.rnum ! b.rnum) return a.rnum b.rnum; return a.num b.num; } int main() { int n; cin n; vectorItem v; v.reserve(n); for (int i 1; i n; i) { v.push_back({i, reverseNum(i)}); } sort(v.begin(), v.end(), cmp); for (int i 0; i n; i) { if (i) cout ; cout v[i].num; } cout \n; return 0; }这里有两个容易被忽略但很实用的点。一是v.reserve(n)。当你知道 vector 最终会有多少个元素时提前reserve可以避免多次扩容拷贝。这道题数据量小不写也能过但好习惯要从小题目开始养。二是输出分隔符的处理。if (i) cout ;这种方式保证行尾没有多余空格。很多 OJ 对行尾空格并不敏感但有些评测系统或者校对脚本会把行尾空格当作错误别再赌这个了。3.2 手算验证 N20 的输出写完代码不能直接交先拿小数据手工验算一遍。N20 时倒序数表如下原数 1 到 9 的倒序数就是它们本身10 的倒序数是 111 的倒序数是 1112 是 2113 是 3114 是 4115 是 5116 是 6117 是 7118 是 8119 是 9120 的倒序数是 2。把倒序数分组来看倒序数为 1 的原数有1、10按原数升序就是 1、10倒序数为 2 的原数有2、20按原数升序就是 2、20倒序数为 3 到 9 的原数分别是 3、4、5、6、7、8、9倒序数为 11、21、31、41、51、61、71、81、91 的原数分别是 11、12、13、14、15、16、17、18、19。所以最终输出是1 10 2 20 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19验证代码逻辑是否一致排序时先比较rnum1和10的rnum都为 1于是走return a.num b.num1 排在 10 前面2和20同理。这个输出和代码行为完全对得上。再试 N10倒序数分组只有 1 和 10 的倒序数同为 1其余 2 到 9 的倒序数分别是自己所以输出是1 10 2 3 4 5 6 7 8 9。这个例子对检查相等时是否按原数升序很有效。3.3 构造边界数据测试提交之前还应该测几个边界N1循环只生成一个数 1输出1。这个用例主要防止数组越界、空输出这类低级错误。N99倒序数会出现两位数交叉的情况。比如 21 的倒序数是 12所以 21 会排在倒序数为 13 的 31 前面而 12 的倒序数是 21所以 12 要排在比较靠后的位置。多写几组手算能帮你确认比较规则没有写反。N100注意 100 的倒序数是 1所以 100 会挤到 1 附近而不是待在倒数位置。这个用例特别能检验对前导零丢弃的理解。我个人的习惯是每次写完排序题都至少构造一个会出现相等排序键的用例和一个末尾带 0的用例跑不对就往下调跑对了再谈优化。4. 实战踩坑这些错误我全犯过每一行都有代价4.1 rev 函数对 0 的处理要小心如果题目数据范围写的是正整数0 不会出现但有的版本可能给出 0 ≤ N或者在自定义比较器里把 0 也当作合法输入。while (x 0)的写法对rev(0)返回 0这是正确的。但如果你图省事改成do...whileint rev(int x) { int r 0; do { r r * 10 x % 10; x / 10; } while (x); return r; }当x0时循环先执行一次r 0结果还是 0看起来也正确。但如果题目要求把 0 的倒序数当作 0那这个写法也没有问题。问题出在有些同学把do...while改成了先除以 10 再取余或者在while条件里写while(x ! 0)导致x为负数时死循环。这类细节只有测边界数据才会暴露。4.2 比较规则不完整结果就是看起来没排序这是这个题最大的坑。如果你只写bool cmp(int a, int b) { return reverseNum(a) reverseNum(b); }那么 1 和 10 的倒序数都是 1cmp(1, 10)返回 falsecmp(10, 1)也返回 false。在 sort 看来这两个元素是等价的谁在前谁在后都由内部排序算法的具体行为决定。标准库的sort是不稳定排序可能会把 10 放到 1 前面于是输出变成10 1 2 20 3 ...看起来就像是排序排岔了。这不是玄学而是稳定性和严格弱序的问题。cmp必须对任意两个元素给出确定的前后关系除非这两个元素在题目意义上完全等价。但题目要求倒序数相同按原数升序所以 1 和 10 并不等价必须在比较器里补上if (reverseNum(a) ! reverseNum(b)) return reverseNum(a) reverseNum(b); return a b;这样cmp(1, 10)会返回 true因为原数 1 小于 10。在信息学竞赛里宁可多写一个if也不要依赖 sort 的运气。4.3 数组下标从 1 开始导致的排序区间错误很多教材在讲排序时喜欢让数组下标从 1 开始比如int a[1005]; for (int i 1; i n; i) { a[i].num i; a[i].rnum reverseNum(i); } sort(a 1, a n 1, cmp);这里的排序开始位置是a 1不是a。如果写成sort(a, a n, cmp)会把第 0 个元素纳入排序却漏掉数组末尾的a[n]。这种错误在本地小数据上不一定能发现因为未初始化的a[0]可能恰好不影响最终输出顺序但一旦 N 变大或者数据排列比较刁钻就会莫名其妙 WA。如果你用vector就不会有这个问题sort(v.begin(), v.end(), cmp)天然覆盖所有元素。这也是我推荐初学者优先用vector的原因之一。4.4 老编译环境的两个兼容性问题信息学竞赛里常见的老版本 Dev-C 5.11 默认编译器是 GCC 4.9.2标准模式不一定支持 C11 的 lambda 表达式和auto。如果你在本地写 lambda提交到 OJ 后编译报错不要觉得奇怪先检查一下题目要求的 C 标准。bits/stdc.h这个万能头文件在 NOI 系列比赛和多数 OJ 上可以正常使用但在部分学校机房或在线平台会提示找不到文件。这道题只需要iostream、vector、algorithm三个头文件规规矩矩写比什么都稳。我一直建议提交前把万能头替换成标准头成本不高收益是少踩一个环境依赖的坑。4.5 输出格式问题常见的输出格式错误有行尾多一个空格、没换行、输出顺序多了一个数。数据范围小的时候行尾空格一般不会判错但如果你养成了多打一个空格无所谓的习惯后面做字符串处理题时会吃亏。用if (i) cout ;这个写法几秒钟就能改完建议直接内化成肌肉记忆。5. 从这道题延伸出去排序题的通用方法论5.1 用冒泡排序理解比较规则和稳定性的关系如果你还没完全理解稳定性是什么可以自己手写一遍冒泡排序来感受struct Item items[1005]; for (int i 1; i n; i) { for (int j 1; j n - i; j) { if (cmp(items[j 1], items[j])) { swap(items[j], items[j 1]); } } }注意条件是cmp(items[j 1], items[j])意思是只有当后一个元素应该排在前一个元素前面时才交换。如果两个元素的倒序数相同且原数也相同cmp返回 false就不会交换从而保持了原有顺序。这就是稳定排序的本质。用冒泡排序实现这道题完全能过但时间复杂度是 O(N²)N 一大就不行了。不过它的好处是让你直观看到比较规则决定了什么算乱序交换与否决定了稳定性是否被破坏。理解了这层再去看sort的底层实现通常是快速排序不稳定就会更清楚为什么必须在cmp中把相等情况处理干净。5.2 同类按规则排序题目的套路这道题本质上属于自定义排序键这一类问题信息学奥赛中还有大量同款按绝对值排序cmp里比较abs(a)和abs(b)按字符串长度排长度相同按字典序cmp里先比len再比字符串内容按分数从高到低排分数相同按学号从小到大这种一般用结构体存分数和学号排序键是两个字段结构体排序中的多关键字排序先按第一关键字再按第二关键字三级四级同理。共同思路是三步提取排序键 → 明确相等规则 → 写进比较器。这道近似排序把这三步压缩在了一个小题目里非常适合作为模板题反复练习。5.3 我建议的学习路径拿这道题来说不要满足于 AC 就关掉页面。至少做三件事第一用结构体写一版再用 lambda 写一版对比两种写法在易错点上的差异。第二把cmp里的相等规则注释掉重新运行观察 N20 时 1 和 10 的顺序是否变化。这一步能让你真正记住不稳定排序 等价元素 结果不确定。第三把 N 分别设成 10、20、50、99手算前三组输出再和程序结果比对。你会慢慢发现凡是末尾带 0 的数都会向倒序数等于某一位数字的位置聚拢这种直觉对以后做数位拆分相关的题目很有帮助。最后说一个我自己的习惯每次做完排序题都会手动演算几组数据并且故意构造边界输入比如 N1、N10、N100、N200确认反转函数和比较规则在各种情况下都不翻车。近似排序这个题看着小但数字反转的写法、自定义排序规则、稳定性处理这三样东西在后面的字符串排序、结构体排序、甚至带权排序里都会反复出现。把它吃透比急着往下刷好几十道题都值。