C++信息学奥赛：近似排序中的数字反转与自定义排序规则

信息奥赛课课通（C++）第154页第1题，标题叫"近似排序"。我第一次看到这四个字时，第一反应是"按与某个目标值的接近程度排序"，直到把题面读完才反应过来，它其实是在处理一件很朴素的事：把 1 到 N 之间每个整数的十进制数字倒过来写，得到一个新的数，然后按这个新数从小到大排序。数字短的时候看不出难度，一旦牵扯到 10、20 这类末尾带 0 的数，排序结果会跟你直觉里的输出完全不一样。这道题非常适合拿来练三样东西：数字拆位、排序规则的定制、以及排序稳定性对结果的影响。如果你刚接触 C++，或者正准备信息学奥赛入门组的比赛，这题值得一道一道抠透。

1. 先拆题："近似"到底在说什么，考点藏在哪里

1.1 最容易被误读的题名

很多同学看到"近似排序"四个字，会往"近似算法""约等于"的方向想，实际上这道题跟"近似"没有任何关系。教材里最常见的题面描述是：输入一个正整数 N，把 1 到 N 的所有整数按"倒序数"从小到大排序并输出。所谓倒序数，就是把一个数的十进制数字顺序完全反过来，比如 123 的倒序数是 321，10 的倒序数是 1，100 的倒序数也是 1。

为什么叫"近似"？因为最终的序列跟原数的自然顺序相比，像是"被倒序数打乱后的近似结果"。比如 N=20 时，1 到 20 对应的倒序数是：

• 1 → 1
• 2 → 2
• ...
• 9 → 9
• 10 → 1
• 11 → 11
• 12 → 21
• 13 → 31
• 14 → 41
• 15 → 51
• 16 → 61
• 17 → 71
• 18 → 81
• 19 → 91
• 20 → 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 为例：

1. 123 % 10 = 3，把 3 放入r，此时r = 3，x变成 12。
2. 12 % 10 = 2，r = 3 * 10 + 2 = 32，x变成 1。
3. 1 % 10 = 1，r = 32 * 10 + 1 = 321，x变成 0，循环结束。

关键点在于r = r * 10 + x % 10这一步：r * 10相当于把已经拼出来的数字整体往左挪一位，腾出个位给当前数的个位。这个过程跟十进制位权的本质完全对应。

特别要注意末尾带 0 的数：比如 10，第一次取余得到 0，此时r还是 0，x变成 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; vector<Node> 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; vector<int> 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 写法在刷小数据量题目、写测试代码时很省事，但不要成为唯一的选择。

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; vector<Item> 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 手算验证 N=20 的输出

写完代码不能直接交，先拿小数据手工验算一遍。N=20 时，倒序数表如下：

原数 1 到 9 的倒序数就是它们本身；10 的倒序数是 1；11 的倒序数是 11；12 是 21；13 是 31；14 是 41；15 是 51；16 是 61；17 是 71；18 是 81；19 是 91；20 的倒序数是 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

验证代码逻辑是否一致：排序时先比较rnum，1和10的rnum都为 1，于是走return a.num < b.num，1 排在 10 前面；2和20同理。这个输出和代码行为完全对得上。

再试 N=10，倒序数分组只有 1 和 10 的倒序数同为 1，其余 2 到 9 的倒序数分别是自己，所以输出是1 10 2 3 4 5 6 7 8 9。这个例子对检查相等时是否按原数升序很有效。

3.3 构造边界数据测试

提交之前还应该测几个边界：

• N=1：循环只生成一个数 1，输出1。这个用例主要防止数组越界、空输出这类低级错误。
• N=99：倒序数会出现两位数交叉的情况。比如 21 的倒序数是 12，所以 21 会排在倒序数为 13 的 31 前面；而 12 的倒序数是 21，所以 12 要排在比较靠后的位置。多写几组手算，能帮你确认比较规则没有写反。
• N=100：注意 100 的倒序数是 1，所以 100 会挤到 1 附近，而不是待在倒数位置。这个用例特别能检验对前导零丢弃的理解。

我个人的习惯是，每次写完排序题，都至少构造一个"会出现相等排序键"的用例和一个"末尾带 0"的用例，跑不对就往下调，跑对了再谈优化。

4. 实战踩坑：这些错误我全犯过，每一行都有代价

4.1 rev 函数对 0 的处理要小心

如果题目数据范围写的是正整数，0 不会出现，但有的版本可能给出 0 ≤ N，或者在自定义比较器里把 0 也当作合法输入。while (x > 0)的写法对rev(0)返回 0，这是正确的。但如果你图省事改成do...while：

int rev(int x) { int r = 0; do { r = r * 10 + x % 10; x /= 10; } while (x); return r; }

当x=0时，循环先执行一次，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 的倒序数都是 1，cmp(1, 10)返回 false，cmp(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，标准模式不一定支持 C++11 的 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里的相等规则注释掉，重新运行，观察 N=20 时 1 和 10 的顺序是否变化。这一步能让你真正记住"不稳定排序 + 等价元素 = 结果不确定"。

第三，把 N 分别设成 10、20、50、99，手算前三组输出再和程序结果比对。你会慢慢发现，凡是末尾带 0 的数都会向"倒序数等于某一位数字"的位置聚拢，这种直觉对以后做数位拆分相关的题目很有帮助。

最后说一个我自己的习惯：每次做完排序题，都会手动演算几组数据，并且故意构造边界输入，比如 N=1、N=10、N=100、N=200，确认反转函数和比较规则在各种情况下都不翻车。"近似排序"这个题看着小，但数字反转的写法、自定义排序规则、稳定性处理，这三样东西在后面的字符串排序、结构体排序、甚至带权排序里都会反复出现。把它吃透，比急着往下刷好几十道题都值。