做这套题时我最初的提交记录特别丢人——先写了个裸的sort直接交数据量不大过了但我自己清楚这种写法对“寻找大富翁”可以说毫无解释力。题目考的是排序可你要真只会调库那“归并排序”四个字就永远只是课本上的概念不是手里能用的工具。后来我老老实实用归并排序重写了一遍才发现这道看似人畜无害的题里藏着不少细节从合并方向到临时数组的复用每一个决定都影响你能不能写出干净、稳定、不超时的代码。这篇就把我的完整实现思路、踩过的坑、以及在Top-M场景下不同排序方案的取舍整理出来。如果你正在刷PTA、准备数据结构考试或者单纯想把归并排序吃透这篇应该对你有用。1. 题目背后真正要考的两件事1.1 Top-M问题为什么不能只靠一个sort交差“寻找大富翁”的题目描述很直白给你N个人的财富值让你输出排在前M位的那些数字。第一反应基本都是全排一遍然后取前M个C里sortC里qsort一行搞定。如果评测数据不算刁钻这确实能过我自己就这么交过。但这类题的设置意图从来不是让你秀库函数。它真正的考点是当“只需要前M个结果”和“必须对所有数据排序”之间存在信息量差异时你会不会做取舍。排序库再好用遇到海量数据、外部存储、流式输入这些场景就必然不够用。而且把全部N个数排好序再截断前M个做了大量不该做的无用功只是在“数值规模不夸张”的时候这种无用功被系统宽容了而已。所以我对这道题的定位是它不只是在考你会不会写排序代码而是在考你能不能理解排序算法的复杂度边界、稳定性含义以及针对“Top-M”这一目标主动做算法选型。等到细节层面归并排序的分治过程天然适合作为讲解载体——它不挑数据分布最坏情况也是O(N log N)这一点比快排安全得多。1.2 归并排序在“大富翁”场景中的天然适配点如果只看“前M大财富值”归并并不是唯一解但它有几个别的方案不太容易替代的优点。第一是复杂度稳定。快排在平均情况下O(N log N)可一旦数据是逆序或近似逆序如果基准点选得不好最坏能退化到O(N²)。归并排序没有这个问题无论输入是什么分布它都固定分治、递归、合并跑满O(N log N)。第二是稳定排序。题目如果只让你输出财富值稳定性用不上但很多变体题会在财富相同的情况下要求按输入顺序输出这时归并的“相等元素保持原相对次序”就是决定性优势。第三是扩展性好。逆序对计数、链表排序、外部多路归并整套体系都建立在归并思想上练熟这一题等于给后面好几类题打了地基。在“寻找大富翁”这个具体例子里正确的做法其实很简单对N个元素做降序归并排序取前M个输出。接下来要解决的就是怎么把归并排序写得不犯错以及怎么处理M可能大于N、输出空格、多组输入这些细节。2. 动手写归并前的三个设计决策2.1 降序合并比较符号与稳定性的取舍归并排序的核心是一个merge函数把两个已经有序的子数组合并成一个大的有序数组。题目要输出“前M名大富翁”我选择直接合并成降序序列。怎么定降序合并时两个子数组各自都是降序的各有一个指针指向当前头部的较大值。比较这两个值谁大谁就先放进结果数组。关键来了如果两个值相等先取哪一边如果写的是if (a[i] a[j])相等时取左边子数组的元素这是稳定排序如果写的是if (a[i] a[j])相等时取右边稳定性就丢了。对于这道题相等取哪边都不影响财富值输出但我建议一律写成。原因很现实稳定排序的定义是“关键字相等时保持原相对顺序”这也是归并排序区别于其他O(N log N)算法的重要标签。养成写的习惯以后遇到按多个关键字排序的题才不会栽跟头。2.2 递归还是迭代性能和递归边界的权衡归并排序有两种常见实现路径。递归版叫自顶向下逻辑直观先拆到单个元素再回溯合并迭代版是自底向上先按长度为1、2、4……的块逐层合并。我的建议第一次手写用递归版。它和分治思想的对应关系最清晰调试时也容易定位问题。迭代版虽然省去了递归调用但边界条件比如最后一组块长度不足怎么办反而更容易把人绕晕。这道题的N虽然可能很大但递归深度只有log₂N层根本不会爆栈不需要为了省这一点点调用开销去牺牲可读性。你真正需要注意的是递归过程中子区间划分的边界是否写对这一点我在后文的踩坑部分会详细讲。2.3 临时数组的复用避免每层mallocmerge函数需要一个临时数组来承接合并结果。最差的写法是在每次merge的时候都malloc一块新内存把合并结果放进去再释放。功能上没问题但排序过程中merge会被调用O(N)次频繁分配内存会让常数时间变大内存碎片也会影响性能一不小心还可能触发内存超限。正确的做法是在最外层一次性申请一块和原数组等大的临时数组然后把它一路传给每一层merge使用。merge结束后再把临时数组对应区间的数据拷贝回原数组。这样整趟排序只分配一次内存逻辑也清爽。别小看这个选择我在本地测试时每次merge都malloc的版本比复用临时数组的版本慢了将近一倍。3. 完整可AC的归并排序实现3.1 递归版核心merge函数逐行拆解先给出递归版的完整核心代码环境是C语言其他语言思路完全一致。#include stdio.h #include stdlib.h // 合并两个有序子数组 a[left..mid] 和 a[mid1..right] // 合并结果为降序结果先放入tmp再拷贝回a void merge(int a[], int tmp[], int left, int mid, int right) { int i left; // 左子数组指针 int j mid 1; // 右子数组指针 int k left; // 临时数组指针 while (i mid j right) { if (a[i] a[j]) { tmp[k] a[i]; } else { tmp[k] a[j]; } } // 左侧还有剩余元素直接追加 while (i mid) { tmp[k] a[i]; } // 右侧还有剩余元素直接追加 while (j right) { tmp[k] a[j]; } // 把这一段的合并结果写回原数组 for (i left; i right; i) { a[i] tmp[i]; } } // 递归版归并排序 void mergeSort(int a[], int tmp[], int left, int right) { if (left right) { return; } int mid (left right) / 2; mergeSort(a, tmp, left, mid); mergeSort(a, tmp, mid 1, right); merge(a, tmp, left, mid, right); }merge函数里的三个while是必须完整的。第一个while处理两个子数组都没耗尽时的大小比较第二个while处理左子数组还有剩余第三个while处理右子数组还有剩余。有人偷懒只写第一个while导致每轮都丢元素排序结果永远不对。最后的for循环也别忘了合并完成后必须把tmp区间的数据复制回原数组a。因为上层递归的merge在合并更大的区间时要求它的两个子区间已经是有序状态如果不回写原数组下一轮拿到的就还是乱序数据。3.2 迭代版自底向上的写法迭代版更接近“归并”的本质先让每个单独元素自成一个长度为1的有序块然后依次把相邻的两个有序块合并成更大块逐步扩大块长度直到整个数组有序。void mergeSortIter(int a[], int tmp[], int n) { for (int len 1; len n; len * 2) { for (int left 0; left n - len; left 2 * len) { int mid left len - 1; int right (left 2 * len - 1 n - 1) ? (left 2 * len - 1) : (n - 1); merge(a, tmp, left, mid, right); } } }外层循环的len是当前要合并的块长度每次都翻倍。内层循环每次取两个长度为len的相邻块左边起点是left左块范围是[left, mid]右块范围是[mid1, right]。right不能超过n-1所以要用条件表达式截断。注意内层循环的结束条件是left n - len这保证了右边确实还存在至少一个元素而不是空块。如果写成left n最后一轮可能会对不存在的右块做无意义的merge虽然大多时候不会出错但边界不严谨就是隐患。3.3 主函数与输出格式处理末尾空格、M截断主函数里要处理几个容易栽跟头的细节多组数据输入、M大于N、输出格式。int main() { int n, m; // 如果平台是单组输入可以去掉while循环 while (scanf(%d%d, n, m) 2) { if (n 0 m 0) { break; } int *a (int *)malloc(n * sizeof(int)); int *tmp (int *)malloc(n * sizeof(int)); for (int i 0; i n; i) { scanf(%d, a[i]); } // 如果M比N还大“前M个”最多就是N个 if (m n) { m n; } mergeSort(a, tmp, 0, n - 1); for (int i 0; i m; i) { if (i 0) { printf( ); } printf(%d, a[i]); } printf(\n); free(a); free(tmp); } return 0; }输出空格的处理我用的是“第一个数前不输出空格”的套路循环里判断i 0才输出空格这样序列末尾不会有多余空格评测系统对末尾空格一般容忍但某些严格模式下会判Presentation Error干脆一开始就避开。M大于N的情况也必须处理如果M确实是100但总共只有50个富翁你总不能输出50个数后还尝试访问a[51]吧那要么越界要么输出垃圾值先m n截断是最稳妥的。4. 实测对比归并、sort、堆、快选怎么选我在这道题上实测过几种方案也观察过不同数据规模下的表现。把这几种常见思路放在一张表里对比会更清楚它们各自的适用边界。方案时间复杂度额外空间稳定性适用场景我的评价全排序取前MsortO(N log N)O(log N) 栈不稳定N不大、追求快速AC能过题但学不到东西归并排序全排O(N log N)O(N)稳定所有N结构稳定推荐作为基本功掌握最小堆维护Top-MO(N log M)O(M)无N极大且M远小于N大数据量下的正确姿势快速选择nth_element平均O(N)O(log N) 栈无只求单个第M大不能有序输出前M个先说sort。如果是单数据情况直接sort全排再取前M个代码最短效率通常也能过。但你要知道这种做法在“只取前M”这件事上一点也不聪明N100万、M10时它把100万个元素全排好了但真正要的只是前10个。再说最小堆。维护一个容量为M的小顶堆遍历所有财富值如果当前值比堆顶大就替换堆顶并调整堆。这样堆里始终保存着当前最大的M个数复杂度O(N log M)空间只有O(M)。当M远小于N时这是效率最高的方案。缺点是最后堆里的元素顺序是乱序如果要按从大到小输出还得再排一次。归并排序在这一点上更直接排完就是有序序列直接输出前M个。最后说快速选择。它的平均复杂度O(N)但得到的结果只能保证第M大的数字就位前M个数字之间的相对顺序是乱序。题目要求完整输出前M个有序数时还得补一轮排序性价比反而不如归并。所以我的结论是如果目的是AC选sort或堆如果目的是打通排序算法体系、应对手写排序的考题归并排序必须能手写出来。从这道题的设置来看考官想看到的是后者。5. 这道题最容易踩的四个坑5.1 递归边界写错导致死循环归并排序递归版的核心是把区间分成[left, mid]和[mid1, right]两段。最容易犯的错是把第二段的左边界写成mid也就是递归调用时写成了mergeSort(a, tmp, mid, right)。这样写会造成什么结果当区间长度为2时比如left0, right1mid0第二段递归变成mergeSort(a, tmp, 0, 1)和第一段一模一样无限递归直接死循环程序卡住或者栈溢出。检查办法很简单在递归函数入口加一条判断如果left right直接返回。只要区间划分正确递归深度是有限的永远不会死循环。5.2 合并时临时数组拷贝不完整merge函数里两个子数组长度不一定相等所以第一个while结束后左边或右边必然有一个没耗尽。必须分别用两个while把剩余元素全部追加到tmp中。有人图省事合并的时候只写了第一个while后面的剩余元素直接丢弃导致每次合并都少元素最终排序结果长度都不对。还有一种隐蔽的错误最后那个for (i left; i right; i)起始位置写成了0。如果把tmp[0..]拷回a[0..]而不是a[left..right]原本在[left, right]之外的数据会被覆盖排序结果面目全非。记住tmp数组只是工作区每次都只操作与本次merge区间对应的那一小段起始位置必须从left开始。5.3 输出多余空格 / 读入超时格式问题看起来小实际很影响提交体验。我见过不少同学代码逻辑全对就是每行末尾多了一个空格被判定为Presentation Error纠结半天才发现不是算法问题。用我上面展示的if (i 0) printf( )写法可以彻底规避。读入超时是另一个隐蔽问题。如果平台数据量大C里直接用cin而不关同步可能会被卡输入输出。我一般建议这种题用C语言的scanf和printf读取输出都快也省去设置同步关闭的麻烦。用C的话记得加ios::sync_with_stdio(false); cin.tie(0);原理是断开cin和scanf、cout和printf之间的同步减少缓冲区刷新次数。5.4 想当然“只排前M个”导致WA我的错误剪枝体验我最初做这道题学归并时觉得反正只输出前M个那我只需要保证排序后前M个位置有序就行了。于是自作聪明在递归入口加了一句if (left m) return;想着下标从m开始的子区间根本不会被输出不排也罢。结果提交后WA本地样例却怎么测试都对。后来我把现象想明白了归并排序的过程是“边比较边交换位置”右侧区间的大数是通过一次次merge被交换到左边来的。如果在递归阶段就把右侧区间整体跳过那么在尚未合并之前它们根本没有机会和左侧元素比较自然也就无法进入前M个位置。前M个位置最后拿到的并不是真正的前M大的数。这个教训很值钱在归并排序完成之前任何子区间都可能包含全局前M大的候选值不能仅仅因为它的下标靠后就跳过排序。真想优化Top-M场景应该选择堆方案或者先做分区而不是在归并排序上硬加剪枝。6. 从寻找大富翁延伸到其他应用6.1 逆序对计数学完归并排序后很多排序题会进阶到“统计数组中的逆序对数量”。逆序对的定义是如果存在ij但a[i]a[j]这对元素就叫一个逆序对。暴力解法O(N²)在大数据量下必挂。用归并排序解决逆序对计数的思路是在合并两个有序子数组时如果取右侧元素也就是a[j]小于等于a[i]的情况说明左侧子数组中从当前指针i到mid的所有元素都大于a[j]这些元素与a[j]构成的逆序对个数就是mid - i 1。每次合并时把这些数量累加排序完成后逆序对总数也统计完了。这个扩展非常自然因为归并排序本身就包含“跨子数组的元素比较”环节逆序对计数只是顺手多算一步。6.2 链表归并排序数组归并排序的缺点是额外O(N)空间但链表排序不一样。链表归并排序不需要临时数组只需要修改节点指针空间复杂度是O(1)。它可以递归写也可以自底向上写。自底向上的版本先按长度为1的链表块两两合并再按长度为2、4……递增直到整条链表有序。这也让“归并排序”成为链表场景下的首选排序算法——快排在链表上不好做随机访问堆排序需要下标只有归并排序能稳定高效地完成。6.3 外部排序思想当数据量大到内存根本装不下时排序就要靠外部排序了。外部排序的流程是把海量数据切成若干块每块能完整读入内存对每块做普通排序后写回磁盘然后从所有有序块中每次读取一部分数据用多路归并的思路把它们逐步合并成一个全局有序的文件。归并排序在这个场景里不仅是排序算法更是核心框架。理解了这一点再回头看“寻找大富翁”你会发现它其实是一个压缩版的外部排序问题——N个数据就是那个“海量文件”M个结果就是最后要保留的有序输出。归并排序从头到尾贯穿了这道题的价值也贯穿了整个排序算法知识体系。最后再分享一点个人体会我后来在很多题目里都把归并排序当兜底方案用因为它的复杂度不依赖输入数据分布不会像快排一样在极端数据里翻车。这次为了写清楚“寻找大富翁”这道题我又把这个基础算法认真重写了一遍那些之前觉得“没必要深究”的比较方向和临时数组细节在调试时全都变成了实打实的经验。如果你也正卡在某个排序题上别急着看题解先把手写归并跑通你会感谢自己这个选择。