这道题我在带学生刷《信息奥赛课课通》的时候就遇到过每次讲到排序那章都会拿“近似排序”出来做课堂练习。别看它只是教材里的一道课后题题面不长、难度也不高但里面藏的东西比看起来多得多——字符串处理、数字拆分、自定义排序规则、多关键字比较全揉在一个入门级别的题目里。很多人刷题图快用sort把结果一跑就过了但这道题恰恰是理解“排序的本质是依据什么”的绝佳样本。这篇文章我就以这道p154-1 近似排序为线索把题目结构拆开把实现方案一步步搭起来再把手写排序和sort自定义规则的细节逐个讲透。不管你是刚开始学C的竞赛新手还是准备带学生的教练这篇文章应该都能给你一点能直接拿去用的东西。1. 题目到底在问什么先还原“近似排序”的完整场景1.1 从教材定位看题目意图《信息奥赛课课通》这本书的定位是信息学竞赛入门教材里面的题目通常不会一上来就考高级数据结构而是把竞赛里常用的基础能力拆成一个个小问题来练。P154 这一页出现“近似排序”从页码位置看基本对应着排序相关章节的中后段。也就是说做这道题的前提是你已经掌握了最基础的排序手法——不管是冒泡排序、选择排序还是sort函数至少得会一种。那这道题具体长什么样虽然不同印刷版本的文字表述可能略有差异但核心意思一般是这样的输入若干正整数将每个数倒过来读得到一个“近似数”。比如 123 的近似数是 321120 的近似数是 21前导0不算。把所有数按照它们的“近似数”从小到大排列。如果两个数的近似数一样则按原始数从小到大排列。请注意最后这句话。它不仅是题目约束也是这道题真正的灵魂。如果只按近似数排序那构造一个一维数组存反转结果再排序就完事儿了。但有了“近似数相同则按原数排”这个规则问题就升级成多关键字排序必须同时保留原数和反转数两个信息否则无法正确恢复最终的输出顺序。所以这道题的关键词其实是两个数字反转和多关键字比较。1.2 “近似”这个叫法是怎么来的很多初学者看到“近似排序”四个字会愣一下心想什么叫近似难道是比较大小的时候允许误差当然不是。这里的“近似”指的是对原始数据做一次变换然后拿变换后的结果去排序。变换本身是一个确定性的映射关系只不过映射之后的数值和原始数值之间不再有直接可比性。举例来说12 和 120 这两个数从原始数值看120 明显大于 12。但它们的反转数分别是 21 和 21在“近似数”这个维度上它俩是相等的。这时候就要启动第二关键字——按原数从小到大排所以最终顺序里 12 应该排在 120 前面。如果题目去掉那个“近似数相同再按原数排”的条件12 和 120 的顺序就变得不确定了sort的不稳定性和比较规则的不严谨就会冒出来。这个设计其实很像竞赛里常见的“按某指标排序指标相同再按原始编号排序”的套路比如成绩排名里总分相同看语文、语文相同看数学。你一旦在入门阶段理解了这种双关键字的处理思想后面遇到结构体排序、成绩排名、任务调度等题目基本都不用再思考直接照搬这个模式。1.3 明确输入输出的坑在竞赛题里输入输出的格式往往是第一个隐形陷阱。“p154-1”的题目输入格式通常是先给一个整数 n表示一共有多少个数然后换行给 n 个正整数数之间用空格或换行分隔。输出则是一行排好序的结果数字之间用空格分隔末尾不能多出多余的空格。这个“末尾不能有多余空格”的要求看起来是件小事但恰恰是新手的重灾区。很多人用循环输出时在每两个数之间输出空格结果最后一个数后面也多打了一个直接被判 Presentation Error。这种错误在竞赛里比 Wrong Answer 还冤因为你的排序逻辑完全正确仅仅因为输出格式不规范就被扣分。我给学生讲这道题的时候通常会直接给他们一个统一的输出模板要么先输出第一个数后面每输出一个数之前加空格要么输出到倒数第二个数时带空格最后一个数单独输出。这个习惯一定要从一开始就养成后面做一百道题都用得上。2. 核心算法拆解数字反转的三种姿势与自定义排序2.1 整除取余法最经典的数字反转要在 C 里把一个数倒过来最直接的做法是用%和/循环取位。以 123 为例reverse 0 第一步reverse reverse * 10 123 % 10 3123 变成 12 第二步reverse 3 * 10 12 % 10 3212 变成 1 第三步reverse 32 * 10 1 % 10 3211 变成 0代码非常简单int reverseNumber(int x) { int rev 0; while (x 0) { rev rev * 10 x % 10; x / 10; } return rev; }这里有几个关键点需要重视循环条件是x 0所以如果输入的正整数本身不包含0函数能正常处理。假如题目允许输入0循环体根本不会执行返回0逻辑也没问题。rev * 10 x % 10这个累加过程会自动消除反转后开头出现的0。120 执行三次循环后得到的 rev 依次是 0、2、21最后返回 21。这正好满足题目里“前导0不算”的要求不需要额外处理。用int存反转数在入门题的数据范围内基本够用。但如果题目把数据范围调大到接近 2^31-1比如 1999999999 这种数反转后是 9999999991明显超出int范围就不得不换成long long。这个函数的本质是“把一个十进制数各位拆出来再以相反的顺序组装”。想明白这一点后面遇到回文数判断、进制转换等题目都是同一套思维。2.2 字符串反转法直观但需要注意性能除了数学方法也可以用字符串来处理反转。先把数字转成字符串用algorithm里的reverse函数反转再转回整数#include iostream #include string #include algorithm using namespace std; int reverseByString(int x) { string s to_string(x); reverse(s.begin(), s.end()); return stoi(s); }这个方法更直观代码量也少stoi在把字符串转回整数时同样会自动丢弃前导0。比如 021 经过stoi变成 21。但有两点要注意stoi在 C11 才加入标准库老旧的教材或在线评测系统如果编译标准太低可能不支持。现在主流的信息学奥赛环境都能用 C11 以上问题不大但如果你在 Visual C 6.0 这类老古董上做题这个方法就行不通。字符串反转涉及类型转换和动态内存分配比纯整数运算慢一点。对于这道题 n 最多可能到几万反转一次无所谓但如果 n 达到百万级别或者反转函数被反复调用字符串法就不是最优选择。我带学生做题时一般建议“两种都要会优先用整除取余法”。原因很简单信息学竞赛是限时比赛花在字符串转换上的时间虽然不多但能省则省。而且竞赛中很多反转类题目不会只反转一个字段往往要同时处理多个整数纯数学方法在性能上更可控。2.3 三种排序实现路径的取舍拿到反转数之后怎么排序有几种路线。路线一结构体 sort 自定义规则这是我最推荐的做法。定义一个结构体把原数和反转数都存进去然后写一个比较函数先比较反转数反转数相同再比较原数#include iostream #include algorithm using namespace std; struct Node { int original; int rev; }; bool cmp(const Node a, const Node b) { if (a.rev ! b.rev) return a.rev b.rev; return a.original b.original; }这个思路最清晰结构体打包数据比较函数定义规则sort负责执行排序。新手写起来不容易乱。路线二只存反转数 手写排序如果你还没学sort也可以用数组分别存原数和反转数然后写一个冒泡排序在交换的同时交换两个数组。这种方法在教学上能帮你理解排序过程中数据的同步移动但代码写起来容易漏掉其中一个数组的交换导致排序结果和原数对不上。路线三用 pair 或 tuple 简化结构体C 自带pair类型可以直接把反转数放在 first原数放在 second然后让sort按照 pair 的默认比较规则排序——first 优先相等时再看 second。这个方案非常巧妙代码量比结构体更少#include iostream #include algorithm #include vector using namespace std; int main() { int n; cin n; vectorpairint, int v(n); for (int i 0; i n; i) { int x; cin x; v[i] {reverseNumber(x), x}; } sort(v.begin(), v.end()); for (int i 0; i n; i) { if (i 0) cout ; cout v[i].second; } return 0; }pair的默认排序规则恰好是“第一关键字优先第二关键字其次”和题目要求完全吻合。这也是为什么我建议你在入门阶段就把pair用熟它后面会频繁出现在图论、贪心算法、动态规划的代码里。我个人在实际教学中的顺序是先让学生用结构体做法把逻辑彻底想通再让他们改成 pair 简化代码。两个版本都写一遍这道题才算真正吃透。3. 从零开始完整实现逐个突破关键环节3.1 预处理数据读入 n 后构建结构体数组完整代码的第一步自然是读入数据。这里有个小细节如果题目要求“读入若干个数直到文件结束”而不是先给 n那你就要用while (cin x)这种循环来读。从教材题目的反推来看p154-1 大概率是“先给 n再给 n 个数”的标准格式所以我按这个格式来写。读入的同时构造结构体数组这一步可以把反转函数直接调用省得后面再遍历一遍#include iostream #include algorithm using namespace std; struct Node { int original; int rev; }; int reverseNumber(int x) { int rev 0; while (x 0) { rev rev * 10 x % 10; x / 10; } return rev; } bool cmp(const Node a, const Node b) { if (a.rev ! b.rev) return a.rev b.rev; return a.original b.original; } int main() { int n; cin n; Node arr[10005]; for (int i 0; i n; i) { cin arr[i].original; arr[i].rev reverseNumber(arr[i].original); } sort(arr, arr n, cmp); for (int i 0; i n; i) { if (i 0) cout ; cout arr[i].original; } return 0; }数组开多大教材到这一章涉及的 n 一般不会超过 1e4所以开 10005 轻轻松松。如果你不确定可以开成vectorNode arr(n)动态分配最稳妥。这个代码的流程分为三步预处理读入并计算反转数、排序按自定义规则、输出。每一段之间是线性的没有嵌套分支逻辑非常直白适合初学者反复阅读并背下来。3.2 手写冒泡排序版本教学价值远超想象如果这部分学习还没讲到sort可以退一步手动实现冒泡排序。这个时候比较规则不要嵌在排序内部而是抽出来作为一个独立的函数这样排序主逻辑和比较逻辑就分开了结构更清楚for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (cmp(arr[j 1], arr[j])) { swap(arr[j], arr[j 1]); } } }这里我故意把比较条件写成cmp(arr[j 1], arr[j])意思是“如果后一个元素应该排在前一个元素前面就交换它们”。这个写法比写if (arr[j].rev arr[j 1].rev)更统一因为当你后续把 cmp 升级为复杂规则时排序代码一个字都不用改。swap函数交换的是整个结构体变量这涉及结构体内部的字节级拷贝。对于只含两个 int 的结构体来说这个开销很小完全不用担心。冒泡排序的复杂度是 O(n²)在 n ≤ 10000 的情况下最坏要跑 1e8 次比较对 1 秒时限来说有点悬但教材题一般时限宽松而且 n 通常给得不大。如果能用sort当然优先sort毕竟 O(n log n) 和 O(n²) 在大数据量下差距是数量级的。但从学习角度手写一遍冒泡能让你意识到“排序的每一趟到底在干嘛”这种理解对后面学习快速排序和归并排序帮助非常大。3.3 比较器返回值的核心语义别搞反了很多初学者在使用sort自定义比较函数时最大的困惑是返回值到底表示什么。这里我用一句大白话解释自定义排序规则bool cmp(int a, int b)返回 true表示 a 排在 b 前面。请注意这里“排在前面”的意思是“在最终排序结果中a 不能出现在 b 的后面”。所以a.rev b.rev返回 true代表反转数小的在前面升序。如果写成a.rev b.rev就变成降序。比较函数必须满足“严格弱排序”的要求同样的两个输入不能分别返回 true否则sort的行为是未定义的可能得到随机顺序甚至崩溃。回到这道题的 cmpif (a.rev ! b.rev) return a.rev b.rev; return a.original b.original;第一行处理“第一关键字”第二行处理“第二关键字”。这种双关键字比较是 cmp 的经典范式值得死记硬背。后面做成绩排名、时间区间排序、任务调度排序全是这个套路。还有一个细节cmp 参数最好用const Node引用传递。虽然这里传值也能过但引用可以避免结构体的拷贝开销并且防止不小心修改原值。这个习惯在竞赛里非常重要因为复杂结构体和 class 的拷贝开销远比两个 int 大。4. 实操错题本这些坑我亲眼见过无数遍4.1 swap 时漏掉同步数据错位的经典翻车如果用两个平行数组a存原数、b存反转数手动排序很容易写出这样的代码if (b[j] b[j 1]) { swap(b[j], b[j 1]); swap(a[j], a[j 1]); }这看起来没问题但如果你少写一句swap(a[j], a[j 1])排序后输出的是a数组就会得到一堆乱序的原数和你算出的反转数完全对不上。这种错误在初学者里特别常见而且不容易用眼睛发现因为反转数排对了但原数和反转数之间的对应关系已经乱了。解决的方法就是不要用两个平行数组。用结构体打包原数和反转数让它们永远待在一起交换的时候整个结构体一起换就从根本上杜绝了这个问题。这也是为什么我一直强调结构体或者 pair 在处理多关键字排序时的优越性——你是在跟一个完整的对象打交道而不是跟两个割裂的数据片段打交道。4.2 反转函数的边界数据范围与0的处理反转函数看似简单实际上有两个容易忽略的边界第一个是数据范围。如果用int接收反转结果而原始数据接近 1e9反转后就可能超过 21 亿导致溢出变成负数。代码逻辑没错结果却是一堆负数参与排序全盘皆输。我的建议是要么在题目允许的范围内用long long要么在反转前判断原始数据的位数避免写出隐患代码。第二个是原始数据包含0的情况。前面说过这个算法对0也能正常工作但如果你的代码里反转函数是用字符串实现的stoi(0)返回0也没问题。真正容易出错的是如果题目里的输入可能包含负整数反转逻辑就不适用了。好在“近似排序”这类题目一般声明输入是正整数遇到负数时你需要先取绝对值再反转最后把符号拼回去——这就属于题目的变种了我建议先保证正整数版本完全掌握再考虑扩展。4.3 输出格式那种“看不见的扣分”信息学奥赛的评测系统对输出格式要求非常严格多一个空格、少一个空格、多一个换行都可能被判为格式错误。初学者最常见的惨案是for (int i 0; i n; i) { cout arr[i].original ; }这会在最后一个数字后面多输出一个空格。看起来没什么大不了但在严格模式下评测系统是拿你输出的字符和标准答案逐字符比对的多出来的空格直接算错误。我推荐的安全写法是“标记法”bool first true; for (int i 0; i n; i) { if (!first) cout ; cout arr[i].original; first false; }或者更简洁的“先输出第一个再循环输出剩余”cout arr[0].original; for (int i 1; i n; i) { cout arr[i].original; }两种写法都能保证末尾没有多余空格。我之前带的几个学生就是因为这个问题反复交了很多次提交最后我把这个模板发到群里要求所有人一律用这种写法之后这类错误基本绝迹。5. 从这道题延伸出去排序思维的地基5.1 把“近似排序”迁移到成绩排名这道题做完之后你会发现它的模式可以套用到任何一个“多关键字排序”问题。最典型的例子是学生成绩排名先按总分排总分相同按数学成绩排数学还相同按语文排。代码几乎一模一样bool cmp(Student a, Student b) { if (a.total ! b.total) return a.total b.total; if (a.math ! b.math) return a.math b.math; return a.chinese b.chinese; }这说明了算法题的本质你记的应该是“模式”而不是“题号”。近似排序的模式就是“先定义一个变换或指标再用这个指标做第一关键字排序原数据做第二关键字”。一旦你识别出某个题目是这个模式20分钟内写出正确代码是完全可行的。反过来看信息学奥赛入门阶段的很多题考的都是这种“模式识别能力”。同一个模式换个场景、改个数据范围、加点限制条件就变成了新题。这也是为什么我建议你在学习每一种排序题时不要满足于把代码跑通而是要问自己如果题目改一下比如反转后按降序排或者要求输出原数的反转数而不是原数我的代码要改哪里想清楚这个题目才真正变成了你的。5.2 排序稳定性为什么“相等也排”很重要这道题还有一个隐藏的小考点排序的稳定性。sort是不稳定排序这意味着如果两个元素的所有关键字都相等它们的相对顺序可能会改变。但在这道题里我们不需要担心这个问题因为题目要求“严格弱排序”——排序规则必须能区分出任意两个元素的大小关系不存在两个完全相等的元素需要保持输入顺序的情况。如果题目改成“仅按反转数排序相同反转数保持输入顺序”这就变成了稳定性排序问题。此时sort就靠不住了你得手写稳定的归并排序或者给每个节点额外加一个输入序号作为第三关键字先比较反转数再比较序号。这也是竞赛里常见的处理方法思路比实现更重要。想通这一点后你会意识到 cmp 里第二关键字的写法根本不是可有可无的补充而是保证排序规则满足严格弱排序的必要条件。没有第二关键字cmp 就失去了对相等元素的明确定义sort的行为就不可控。这算是一个比较容易忽略但很重要的底层原理。5.3 给初学者的一句话总结在准备结束这道题之前我想说一句可能有点老生常谈但非常实在的话刷题的时候代码跑通只是及格线理解你写的每一行代码为什么存在才是真正的得分点。以这道近似排序为例如果你只是背下代码模板那下次遇到“按个位数排序”这样的变种题你还是不会。但如果你吃透了“反转函数 结构体 自定义比较器”这三件套那不管题目怎么包装你都能一眼看穿它在考什么然后快速套用已经内化的模式。根据我个人的教学经验学生在信息学奥赛入门阶段最容易犯的错误就是“重刷题轻总结”。每道题花 20 分钟跑通却不花 5 分钟复盘。如果你想在这个领域走得更远建议从这道近似排序开始养成一个习惯每做完一道题写下这道题的模式是什么、有没有变体、代码里哪个函数可以抽出来复用。这个习惯坚持半年你的竞赛水平会有质变。 近似排序题详解：数字反转与多关键字排序的C++实现
这道题我在带学生刷《信息奥赛课课通》的时候就遇到过每次讲到排序那章都会拿“近似排序”出来做课堂练习。别看它只是教材里的一道课后题题面不长、难度也不高但里面藏的东西比看起来多得多——字符串处理、数字拆分、自定义排序规则、多关键字比较全揉在一个入门级别的题目里。很多人刷题图快用sort把结果一跑就过了但这道题恰恰是理解“排序的本质是依据什么”的绝佳样本。这篇文章我就以这道p154-1 近似排序为线索把题目结构拆开把实现方案一步步搭起来再把手写排序和sort自定义规则的细节逐个讲透。不管你是刚开始学C的竞赛新手还是准备带学生的教练这篇文章应该都能给你一点能直接拿去用的东西。1. 题目到底在问什么先还原“近似排序”的完整场景1.1 从教材定位看题目意图《信息奥赛课课通》这本书的定位是信息学竞赛入门教材里面的题目通常不会一上来就考高级数据结构而是把竞赛里常用的基础能力拆成一个个小问题来练。P154 这一页出现“近似排序”从页码位置看基本对应着排序相关章节的中后段。也就是说做这道题的前提是你已经掌握了最基础的排序手法——不管是冒泡排序、选择排序还是sort函数至少得会一种。那这道题具体长什么样虽然不同印刷版本的文字表述可能略有差异但核心意思一般是这样的输入若干正整数将每个数倒过来读得到一个“近似数”。比如 123 的近似数是 321120 的近似数是 21前导0不算。把所有数按照它们的“近似数”从小到大排列。如果两个数的近似数一样则按原始数从小到大排列。请注意最后这句话。它不仅是题目约束也是这道题真正的灵魂。如果只按近似数排序那构造一个一维数组存反转结果再排序就完事儿了。但有了“近似数相同则按原数排”这个规则问题就升级成多关键字排序必须同时保留原数和反转数两个信息否则无法正确恢复最终的输出顺序。所以这道题的关键词其实是两个数字反转和多关键字比较。1.2 “近似”这个叫法是怎么来的很多初学者看到“近似排序”四个字会愣一下心想什么叫近似难道是比较大小的时候允许误差当然不是。这里的“近似”指的是对原始数据做一次变换然后拿变换后的结果去排序。变换本身是一个确定性的映射关系只不过映射之后的数值和原始数值之间不再有直接可比性。举例来说12 和 120 这两个数从原始数值看120 明显大于 12。但它们的反转数分别是 21 和 21在“近似数”这个维度上它俩是相等的。这时候就要启动第二关键字——按原数从小到大排所以最终顺序里 12 应该排在 120 前面。如果题目去掉那个“近似数相同再按原数排”的条件12 和 120 的顺序就变得不确定了sort的不稳定性和比较规则的不严谨就会冒出来。这个设计其实很像竞赛里常见的“按某指标排序指标相同再按原始编号排序”的套路比如成绩排名里总分相同看语文、语文相同看数学。你一旦在入门阶段理解了这种双关键字的处理思想后面遇到结构体排序、成绩排名、任务调度等题目基本都不用再思考直接照搬这个模式。1.3 明确输入输出的坑在竞赛题里输入输出的格式往往是第一个隐形陷阱。“p154-1”的题目输入格式通常是先给一个整数 n表示一共有多少个数然后换行给 n 个正整数数之间用空格或换行分隔。输出则是一行排好序的结果数字之间用空格分隔末尾不能多出多余的空格。这个“末尾不能有多余空格”的要求看起来是件小事但恰恰是新手的重灾区。很多人用循环输出时在每两个数之间输出空格结果最后一个数后面也多打了一个直接被判 Presentation Error。这种错误在竞赛里比 Wrong Answer 还冤因为你的排序逻辑完全正确仅仅因为输出格式不规范就被扣分。我给学生讲这道题的时候通常会直接给他们一个统一的输出模板要么先输出第一个数后面每输出一个数之前加空格要么输出到倒数第二个数时带空格最后一个数单独输出。这个习惯一定要从一开始就养成后面做一百道题都用得上。2. 核心算法拆解数字反转的三种姿势与自定义排序2.1 整除取余法最经典的数字反转要在 C 里把一个数倒过来最直接的做法是用%和/循环取位。以 123 为例reverse 0 第一步reverse reverse * 10 123 % 10 3123 变成 12 第二步reverse 3 * 10 12 % 10 3212 变成 1 第三步reverse 32 * 10 1 % 10 3211 变成 0代码非常简单int reverseNumber(int x) { int rev 0; while (x 0) { rev rev * 10 x % 10; x / 10; } return rev; }这里有几个关键点需要重视循环条件是x 0所以如果输入的正整数本身不包含0函数能正常处理。假如题目允许输入0循环体根本不会执行返回0逻辑也没问题。rev * 10 x % 10这个累加过程会自动消除反转后开头出现的0。120 执行三次循环后得到的 rev 依次是 0、2、21最后返回 21。这正好满足题目里“前导0不算”的要求不需要额外处理。用int存反转数在入门题的数据范围内基本够用。但如果题目把数据范围调大到接近 2^31-1比如 1999999999 这种数反转后是 9999999991明显超出int范围就不得不换成long long。这个函数的本质是“把一个十进制数各位拆出来再以相反的顺序组装”。想明白这一点后面遇到回文数判断、进制转换等题目都是同一套思维。2.2 字符串反转法直观但需要注意性能除了数学方法也可以用字符串来处理反转。先把数字转成字符串用algorithm里的reverse函数反转再转回整数#include iostream #include string #include algorithm using namespace std; int reverseByString(int x) { string s to_string(x); reverse(s.begin(), s.end()); return stoi(s); }这个方法更直观代码量也少stoi在把字符串转回整数时同样会自动丢弃前导0。比如 021 经过stoi变成 21。但有两点要注意stoi在 C11 才加入标准库老旧的教材或在线评测系统如果编译标准太低可能不支持。现在主流的信息学奥赛环境都能用 C11 以上问题不大但如果你在 Visual C 6.0 这类老古董上做题这个方法就行不通。字符串反转涉及类型转换和动态内存分配比纯整数运算慢一点。对于这道题 n 最多可能到几万反转一次无所谓但如果 n 达到百万级别或者反转函数被反复调用字符串法就不是最优选择。我带学生做题时一般建议“两种都要会优先用整除取余法”。原因很简单信息学竞赛是限时比赛花在字符串转换上的时间虽然不多但能省则省。而且竞赛中很多反转类题目不会只反转一个字段往往要同时处理多个整数纯数学方法在性能上更可控。2.3 三种排序实现路径的取舍拿到反转数之后怎么排序有几种路线。路线一结构体 sort 自定义规则这是我最推荐的做法。定义一个结构体把原数和反转数都存进去然后写一个比较函数先比较反转数反转数相同再比较原数#include iostream #include algorithm using namespace std; struct Node { int original; int rev; }; bool cmp(const Node a, const Node b) { if (a.rev ! b.rev) return a.rev b.rev; return a.original b.original; }这个思路最清晰结构体打包数据比较函数定义规则sort负责执行排序。新手写起来不容易乱。路线二只存反转数 手写排序如果你还没学sort也可以用数组分别存原数和反转数然后写一个冒泡排序在交换的同时交换两个数组。这种方法在教学上能帮你理解排序过程中数据的同步移动但代码写起来容易漏掉其中一个数组的交换导致排序结果和原数对不上。路线三用 pair 或 tuple 简化结构体C 自带pair类型可以直接把反转数放在 first原数放在 second然后让sort按照 pair 的默认比较规则排序——first 优先相等时再看 second。这个方案非常巧妙代码量比结构体更少#include iostream #include algorithm #include vector using namespace std; int main() { int n; cin n; vectorpairint, int v(n); for (int i 0; i n; i) { int x; cin x; v[i] {reverseNumber(x), x}; } sort(v.begin(), v.end()); for (int i 0; i n; i) { if (i 0) cout ; cout v[i].second; } return 0; }pair的默认排序规则恰好是“第一关键字优先第二关键字其次”和题目要求完全吻合。这也是为什么我建议你在入门阶段就把pair用熟它后面会频繁出现在图论、贪心算法、动态规划的代码里。我个人在实际教学中的顺序是先让学生用结构体做法把逻辑彻底想通再让他们改成 pair 简化代码。两个版本都写一遍这道题才算真正吃透。3. 从零开始完整实现逐个突破关键环节3.1 预处理数据读入 n 后构建结构体数组完整代码的第一步自然是读入数据。这里有个小细节如果题目要求“读入若干个数直到文件结束”而不是先给 n那你就要用while (cin x)这种循环来读。从教材题目的反推来看p154-1 大概率是“先给 n再给 n 个数”的标准格式所以我按这个格式来写。读入的同时构造结构体数组这一步可以把反转函数直接调用省得后面再遍历一遍#include iostream #include algorithm using namespace std; struct Node { int original; int rev; }; int reverseNumber(int x) { int rev 0; while (x 0) { rev rev * 10 x % 10; x / 10; } return rev; } bool cmp(const Node a, const Node b) { if (a.rev ! b.rev) return a.rev b.rev; return a.original b.original; } int main() { int n; cin n; Node arr[10005]; for (int i 0; i n; i) { cin arr[i].original; arr[i].rev reverseNumber(arr[i].original); } sort(arr, arr n, cmp); for (int i 0; i n; i) { if (i 0) cout ; cout arr[i].original; } return 0; }数组开多大教材到这一章涉及的 n 一般不会超过 1e4所以开 10005 轻轻松松。如果你不确定可以开成vectorNode arr(n)动态分配最稳妥。这个代码的流程分为三步预处理读入并计算反转数、排序按自定义规则、输出。每一段之间是线性的没有嵌套分支逻辑非常直白适合初学者反复阅读并背下来。3.2 手写冒泡排序版本教学价值远超想象如果这部分学习还没讲到sort可以退一步手动实现冒泡排序。这个时候比较规则不要嵌在排序内部而是抽出来作为一个独立的函数这样排序主逻辑和比较逻辑就分开了结构更清楚for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (cmp(arr[j 1], arr[j])) { swap(arr[j], arr[j 1]); } } }这里我故意把比较条件写成cmp(arr[j 1], arr[j])意思是“如果后一个元素应该排在前一个元素前面就交换它们”。这个写法比写if (arr[j].rev arr[j 1].rev)更统一因为当你后续把 cmp 升级为复杂规则时排序代码一个字都不用改。swap函数交换的是整个结构体变量这涉及结构体内部的字节级拷贝。对于只含两个 int 的结构体来说这个开销很小完全不用担心。冒泡排序的复杂度是 O(n²)在 n ≤ 10000 的情况下最坏要跑 1e8 次比较对 1 秒时限来说有点悬但教材题一般时限宽松而且 n 通常给得不大。如果能用sort当然优先sort毕竟 O(n log n) 和 O(n²) 在大数据量下差距是数量级的。但从学习角度手写一遍冒泡能让你意识到“排序的每一趟到底在干嘛”这种理解对后面学习快速排序和归并排序帮助非常大。3.3 比较器返回值的核心语义别搞反了很多初学者在使用sort自定义比较函数时最大的困惑是返回值到底表示什么。这里我用一句大白话解释自定义排序规则bool cmp(int a, int b)返回 true表示 a 排在 b 前面。请注意这里“排在前面”的意思是“在最终排序结果中a 不能出现在 b 的后面”。所以a.rev b.rev返回 true代表反转数小的在前面升序。如果写成a.rev b.rev就变成降序。比较函数必须满足“严格弱排序”的要求同样的两个输入不能分别返回 true否则sort的行为是未定义的可能得到随机顺序甚至崩溃。回到这道题的 cmpif (a.rev ! b.rev) return a.rev b.rev; return a.original b.original;第一行处理“第一关键字”第二行处理“第二关键字”。这种双关键字比较是 cmp 的经典范式值得死记硬背。后面做成绩排名、时间区间排序、任务调度排序全是这个套路。还有一个细节cmp 参数最好用const Node引用传递。虽然这里传值也能过但引用可以避免结构体的拷贝开销并且防止不小心修改原值。这个习惯在竞赛里非常重要因为复杂结构体和 class 的拷贝开销远比两个 int 大。4. 实操错题本这些坑我亲眼见过无数遍4.1 swap 时漏掉同步数据错位的经典翻车如果用两个平行数组a存原数、b存反转数手动排序很容易写出这样的代码if (b[j] b[j 1]) { swap(b[j], b[j 1]); swap(a[j], a[j 1]); }这看起来没问题但如果你少写一句swap(a[j], a[j 1])排序后输出的是a数组就会得到一堆乱序的原数和你算出的反转数完全对不上。这种错误在初学者里特别常见而且不容易用眼睛发现因为反转数排对了但原数和反转数之间的对应关系已经乱了。解决的方法就是不要用两个平行数组。用结构体打包原数和反转数让它们永远待在一起交换的时候整个结构体一起换就从根本上杜绝了这个问题。这也是为什么我一直强调结构体或者 pair 在处理多关键字排序时的优越性——你是在跟一个完整的对象打交道而不是跟两个割裂的数据片段打交道。4.2 反转函数的边界数据范围与0的处理反转函数看似简单实际上有两个容易忽略的边界第一个是数据范围。如果用int接收反转结果而原始数据接近 1e9反转后就可能超过 21 亿导致溢出变成负数。代码逻辑没错结果却是一堆负数参与排序全盘皆输。我的建议是要么在题目允许的范围内用long long要么在反转前判断原始数据的位数避免写出隐患代码。第二个是原始数据包含0的情况。前面说过这个算法对0也能正常工作但如果你的代码里反转函数是用字符串实现的stoi(0)返回0也没问题。真正容易出错的是如果题目里的输入可能包含负整数反转逻辑就不适用了。好在“近似排序”这类题目一般声明输入是正整数遇到负数时你需要先取绝对值再反转最后把符号拼回去——这就属于题目的变种了我建议先保证正整数版本完全掌握再考虑扩展。4.3 输出格式那种“看不见的扣分”信息学奥赛的评测系统对输出格式要求非常严格多一个空格、少一个空格、多一个换行都可能被判为格式错误。初学者最常见的惨案是for (int i 0; i n; i) { cout arr[i].original ; }这会在最后一个数字后面多输出一个空格。看起来没什么大不了但在严格模式下评测系统是拿你输出的字符和标准答案逐字符比对的多出来的空格直接算错误。我推荐的安全写法是“标记法”bool first true; for (int i 0; i n; i) { if (!first) cout ; cout arr[i].original; first false; }或者更简洁的“先输出第一个再循环输出剩余”cout arr[0].original; for (int i 1; i n; i) { cout arr[i].original; }两种写法都能保证末尾没有多余空格。我之前带的几个学生就是因为这个问题反复交了很多次提交最后我把这个模板发到群里要求所有人一律用这种写法之后这类错误基本绝迹。5. 从这道题延伸出去排序思维的地基5.1 把“近似排序”迁移到成绩排名这道题做完之后你会发现它的模式可以套用到任何一个“多关键字排序”问题。最典型的例子是学生成绩排名先按总分排总分相同按数学成绩排数学还相同按语文排。代码几乎一模一样bool cmp(Student a, Student b) { if (a.total ! b.total) return a.total b.total; if (a.math ! b.math) return a.math b.math; return a.chinese b.chinese; }这说明了算法题的本质你记的应该是“模式”而不是“题号”。近似排序的模式就是“先定义一个变换或指标再用这个指标做第一关键字排序原数据做第二关键字”。一旦你识别出某个题目是这个模式20分钟内写出正确代码是完全可行的。反过来看信息学奥赛入门阶段的很多题考的都是这种“模式识别能力”。同一个模式换个场景、改个数据范围、加点限制条件就变成了新题。这也是为什么我建议你在学习每一种排序题时不要满足于把代码跑通而是要问自己如果题目改一下比如反转后按降序排或者要求输出原数的反转数而不是原数我的代码要改哪里想清楚这个题目才真正变成了你的。5.2 排序稳定性为什么“相等也排”很重要这道题还有一个隐藏的小考点排序的稳定性。sort是不稳定排序这意味着如果两个元素的所有关键字都相等它们的相对顺序可能会改变。但在这道题里我们不需要担心这个问题因为题目要求“严格弱排序”——排序规则必须能区分出任意两个元素的大小关系不存在两个完全相等的元素需要保持输入顺序的情况。如果题目改成“仅按反转数排序相同反转数保持输入顺序”这就变成了稳定性排序问题。此时sort就靠不住了你得手写稳定的归并排序或者给每个节点额外加一个输入序号作为第三关键字先比较反转数再比较序号。这也是竞赛里常见的处理方法思路比实现更重要。想通这一点后你会意识到 cmp 里第二关键字的写法根本不是可有可无的补充而是保证排序规则满足严格弱排序的必要条件。没有第二关键字cmp 就失去了对相等元素的明确定义sort的行为就不可控。这算是一个比较容易忽略但很重要的底层原理。5.3 给初学者的一句话总结在准备结束这道题之前我想说一句可能有点老生常谈但非常实在的话刷题的时候代码跑通只是及格线理解你写的每一行代码为什么存在才是真正的得分点。以这道近似排序为例如果你只是背下代码模板那下次遇到“按个位数排序”这样的变种题你还是不会。但如果你吃透了“反转函数 结构体 自定义比较器”这三件套那不管题目怎么包装你都能一眼看穿它在考什么然后快速套用已经内化的模式。根据我个人的教学经验学生在信息学奥赛入门阶段最容易犯的错误就是“重刷题轻总结”。每道题花 20 分钟跑通却不花 5 分钟复盘。如果你想在这个领域走得更远建议从这道近似排序开始养成一个习惯每做完一道题写下这道题的模式是什么、有没有变体、代码里哪个函数可以抽出来复用。这个习惯坚持半年你的竞赛水平会有质变。