归并排序实战：用分治思想解决“寻找大富翁”Top M问题-北京尧图网络

在 OJ 题库的排序专题里“寻找大富翁”属于那种题目扫一眼就懂、动手写却容易反复提交的经典题。题意本身不难给你一堆人的财产估值输出其中财富排名前 M 位的数字。真正的坎在于数据量。当 N 被抬到十万甚至百万量级冒泡、插入这些 O(N^2) 排序基本提前下课题目实际想考察的是你能不能徒手写出归并排序这种 O(N log N) 的高效算法而不是调库函数应付了事。我第一次做这道题时也走了捷径直接用语言自带的排序函数交上去确实通过了。但二刷时我要求自己必须用归并排序从头写一遍这才发现很多细节并没有吃透临时数组什么时候拷贝回原数组合并时用还是递归到底要压多少层当 M 比 N 还大时输出什么这些坑一个接一个冒出来。这篇文章就把我从“读懂归并排序”到“一次通过寻找大富翁”的完整过程拆开讲适合正在刷排序专题或者想彻底搞懂归并排序实现细节的同学参考。1. 题目还原与考点拆解这道题到底在考你什么1.1 输入输出长什么样按我常用的版本题面是这样第一行给出两个整数 N 和 M第二行给出 N 个整数代表 N 个人的财产估值。要求在一行内按递减顺序输出财富值最大的前 M 个数字数字之间用空格分隔行尾不能有多余空格。我拿两个小用例验证逻辑输入 8 3 1 2 3 4 5 6 7 8 输出 8 7 6 输入 5 2 100 19 25 45 8 输出 100 45这里有个容易被忽略的版本差异有的题目明确保证 M N有的则没有。一旦出现 M N输出要求就变成“全部数都要输出”。很多人在本地测试用例全过交上去却出现数据异常多半就是没处理这个边界后面第 4 章我会专门展开讲。1.2 为什么不能靠“重复找最大值”骗分有些同学看到题目后的第一反应是不用全排序我扫描一遍找到最大值标记后再扫一遍找第二大的重复 M 次不就行了理论上可行复杂度却经不起推敲。每次扫描是 O(N)做 M 次就是 O(NM)。当 M 和 N 都接近上限时这个复杂度跟 O(N^2) 没有本质区别超时是必然的。而且数组不像链表想“删掉”一个已找到的元素还得把后面的元素往前挪这是 O(N) 的搬运成本。如果每次都这么干实际开销比单纯扫描还高。哪怕用标记数组代替删除也只是把常数因子变小数量级没变在 10^5 以上的数据量面前依然不够看。反观归并排序一次完整排序是 O(N log N)。N 10^6 时log₂N 大约 20运算量在千万量级几乎一瞬间。差距就是这么来的。1.3 专题设置里的教学意图很多 OJ 把这道题放在“归并排序”专题或配套作业里教学意图相当明显它不是让你研究怎么调 qsort而是让你亲手实现一趟“拆分-递归-合并”的完整分治流程。归并排序结构规整、逻辑清晰特别适合考察数组下标控制和递归边界把握。通过这道题你能同时练到三件事递归函数的退出条件、两段有序数组的线性合并、以及辅助数组的申请与回写。这也是为什么即使在实际开发里归并排序不常徒手写许多算法课程依然把它列为必练项目——它几乎是分治思想最朴素的教学样板。弄明白归并后面学快速排序、堆排序、二分查找都会顺很多因为它们共享同一套“分而治之”的思维模式。2. 归并排序的分治原理动手前先把三件事想透2.1 分治三步拆、排、并归并排序处理一段长度为 len 的数组时做法是把数组从中间切成左右两半递归地把左半边排好序再把右半边排好序最后把两个有序的小数组按顺序合二为一。以[4, 7, 1, 5, 2, 8, 3, 6]为例第一次切分得到[4, 7, 1, 5]和[2, 8, 3, 6]。继续切到区间只有 1 个元素时它天然有序递归开始返回。合并[4, 7]和[1, 5]时先比较 4 和 11 先入列再比较 4 和 54 入列然后 7 入列5 入列得到[1, 4, 5, 7]。右侧类似地合并出[2, 3, 6, 8]最后再把两个 4 元段合并成完整有序数组。递归的出口就是 low high也就是区间里只有一个元素的时候。这时候什么都不用做直接返回因为单个元素必然有序。整个排序过程不需要额外来判断数组是否为空只要在调用前保证 low high 即可。2.2 合并过程的双指针为什么要这么移动合并是两个有序段变成一个有序段的过程。假设左右两段分别是wealth[low..mid]和wealth[mid1..high]我会用三个下标控制i 指向左段当前位置j 指向右段当前位置k 指向辅助数组 temp 的写入位置。每一步只做一件事比较wealth[i]和wealth[j]。如果左边小就把左边的数放进 tempi 和 k 各前进一位否则把右边的数放进 tempj 和 k 各前进一位。当某一段元素被取完后直接把另一段剩余元素依次写入。因为两段本身有序所以剩余部分一定也有序直接接上即可。这段逻辑里最关键的是比较符号。我强烈建议写成而不是。用能保证两个相等元素中左半数组的那个先被取走它们的相对位置不会颠倒这正是归并排序被称为“稳定排序”的原因。实际工程中如果排序对象不只是数字还携带原始次序或其他属性稳定性就可能直接影响结果正确性。在练习阶段把这些习惯刻进肌肉记忆将来会有回报。2.3 复杂度与辅助空间的账分治过程的递推式是 T(n) 2T(n/2) O(n)。O(n) 来自每一层合并时遍历一遍整个区间递归一共有 log₂n 层所以总复杂度是 O(n log n)。无论输入是否接近有序归并排序的时间波动都很小这是它比快速排序“性格更稳”的原因之一。快排在最坏情况下可能退化到 O(N^2)而归并排序无论是升序、降序还是随机数据都稳定地跑在 O(N log N)。代价是空间。合并时需要一份与待排序区间等长的辅助数组整体空间复杂度达到 O(n)。对于百万量级数据一个 int 数组约 4MB加辅助数组约 8MBOJ 通常给得了。但如果你在函数内部临时声明超大数组可能导致栈溢出或运行时错误所以这类题我一般建议把数组开成全局变量这个细节在第 4 章会进一步展开。3. 完整解题流程与 C 语言实现3.1 递归版归并排序的标准写法下面是我使用的 C 语言实现。两个关键数组直接定义为全局变量既能避免栈空间不足也能方便 merge 函数直接访问不需要每次调用都传参#include stdio.h int wealth[1000005]; int temp[1000005]; void merge(int low, int mid, int high) { int i low; int j mid 1; int k low; while (i mid j high) { if (wealth[i] wealth[j]) { temp[k] wealth[i]; } else { temp[k] wealth[j]; } } while (i mid) { temp[k] wealth[i]; } while (j high) { temp[k] wealth[j]; } for (i low; i high; i) { wealth[i] temp[i]; } } void mergeSort(int low, int high) { if (low high) { int mid (low high) 1; mergeSort(low, mid); mergeSort(mid 1, high); merge(low, mid, high); } }merge 函数里第一个 while 是双指针合并的主体后面两个 while 处理“某一侧剩余”的情况。最后一步把 temp 拷贝回原数组这一步千万别漏否则排序结果不会同步到 wealth 里下一次合并拿到的仍是混乱数据。我见过不少第一次写归并的人在这里翻车排完序一看前半段对、后半段乱几乎都是回写时机或回写范围出了问题。3.2 主函数里有哪些细节主函数代码如下int main() { int n, m; while (scanf(%d %d, n, m) ! EOF) { for (int i 0; i n; i) { scanf(%d, wealth[i]); } mergeSort(0, n - 1); int cnt (m n) ? m : n; for (int i 0; i cnt; i) { if (i 0) { printf( ); } printf(%d, wealth[n - 1 - i]); } printf(\n); } return 0; }我用while (scanf(...) ! EOF)把读取过程写成多组输入的形式。有些版本明确只有一组数据这种写法也能兼容如果输入真的是多组也不会漏读。读取完数据后先对整个数组做升序归并排序然后从数组尾部向前取 cnt 个元素。为什么是wealth[n - 1 - i]因为排序后数组升序排列最大值在最后。想要得到递减的输出序列就得从尾部开始倒着访问。有人会想直接把归并排序改成降序也不是不行把合并里的换成就行。但我习惯保持升序因为升序是排序最自然的默认方向改核心逻辑反而容易引入额外错误。3.3 从“全排序”到“前 M 大”的脑筋急转弯排序完成后输出前 M 个最大值通常有两种姿势一是按升序排完后从尾部取二是直接把数组排成降序。我强烈推荐第一种。理由很简单归并排序写升序最顺手从尾部取值也不需要改变排序方向只需要在输出循环里倒序访问。这样把“排序逻辑”和“输出逻辑”彻底解耦出问题时更容易定位。输出层还有一个常规纪律数字之间用空格最后一个数字后面不要跟空格。我的做法是用if (i 0) printf( );判断这样首个元素前不加空格后续元素前自然补上。很多同学在输出格式上报 Presentation Error基本都是行末空格没处理干净。虽然这种错误不算算法不会但在 OJ 上同样会罚时比赛里每一分钟都很宝贵。4. 每次提交都可能翻车的边界细节4.1 M 大于 N数组越界的隐形杀手如果题目版本不保证 M N而主函数里直接写for (int i 0; i m; i) printf(%d , wealth[n - 1 - i])当 m n 时n - 1 - i会变成负数访问wealth[-1]甚至更低的越界地址结果完全不可预期。轻则输出垃圾值重则段错误OJ 直接给你一个 Runtime Error。这是整道题里最值得刻进肌肉记忆的动作读取两个参数后凡是涉及数组下标第一步先考虑能不能越界。我采用cnt (m n) ? m : n;的方式把输出数量限制在有效范围内。这个写法比if (m n) m n;更紧凑语义也更清晰。还有一点要注意这里的比较是m n不是m n。如果 m n那正好输出全部 n 个数不需要额外处理所以严格小于就够用了。4.2 合并过程里和的区别我见过不少同学在 merge 里写成if (wealth[i] wealth[j])认为只要把小的取走就行。对纯数字排序来说结果确实不会错因为相等元素谁先谁后最终得到的数值集合是相同的。可一旦排序对象不只是数字还携带“原始序号”或需要保持相对次序就会破坏稳定性而且这种破坏很隐蔽——它不影响数值排序结果只在特定场景下悄悄让答案偏离预期。练习归并排序时我建议统一写。这既不是性能问题也不是“必须这样才叫正确答案”而是让你在训练阶段就把稳定排序的行为模式刻进习惯里。将来遇到需要稳定排序的业务场景比如按时间排序再按优先级排序这个习惯能帮你少踩很多坑。4.3 临时数组的申请时机与大小初学者容易把 temp 数组放在 merge 函数内部每次合并都申请一次。这有两个问题一是频繁申请释放带来不必要的开销二是递归合并时栈上空间累积数组一大就很危险。稳妥做法是像第 3 章代码那样把 temp 声明成全局数组容量与 wealth 保持一致并且在读写时严格遵守 low..high 的范围。另一个细节是 temp 的容量。直接用题目数据范围定成 1000005 最省心。如果题目没给范围可以用 malloc 动态分配但要记得检查返回值并且用完 free 掉。不过在 OJ 题里没给范围的情况很少见通常题面或输入规模描述里会有说明定一个略大于上限的常量数组是最不费脑子的选择。4.4 递归深度和迭代版兜底N 达到 10^6 时归并排序的递归深度大约是 log₂1000000也就是 20 层左右C 语言默认函数栈完全扛得住。但在某些极端环境或编译选项下如果把大数组声明在 main 函数里同时递归过程中又有大量局部变量压栈仍然可能出现栈溢出。保险方案有两个数组全部用全局变量或者改用非递归归并排序。非递归版本的思路是自底向上先用宽度 1 的小区间两两合并再宽度 2、4、8……每轮合并相邻的两个宽度一致的区间直到宽度不小于 n。我贴一个常用的实现void mergeSortIterative(int n) { for (int width 1; width n; width 1) { for (int left 0; left n; left width 1) { int mid left width - 1; int right left (width 1) - 1; if (mid n) mid n - 1; if (right n) right n - 1; if (mid right) { merge(left, mid, right); } } } }它复用了同一个 merge 函数只是把递归换成了循环。对于竞赛场景递归版通常已经足够迭代版更像是给那些对栈深度有执念的人准备的保险丝。我自己在平时练习时会把两个版本都写一遍遇到新题目时就能根据环境条件灵活选择。5. 如果题目不点名归并排序还可以怎么解5.1 用小顶堆维护 Top M如果 M 远小于 N比如 M 10、N 10^5其实不需要全排序。维护一个大小为 M 的小顶堆即可堆里永远存放当前遇到的最大 M 个数。读入新数时如果堆没满直接插入如果堆满了且新数比堆顶大就用新数替换堆顶然后向下调整。因为堆顶是这 M 个数里最小的所以新数能进来就说明它是当前全局前 M 大的新成员。最后堆里的 M 个数就是答案。要注意小顶堆输出的顺序是从小到大想得到递减输出还需要额外排一次序或者逐一出堆后再反转。这种方案的时间复杂度是 O(N log M)空间只有 O(M)。但当 M 接近 N 时它和全排序相比没有优势反而要多维护堆结构实现也更复杂。5.2 用快速排序系的做法语言自带的 qsort 或 C 的 sort 也是对数组全排序底层通常是经过优化的快速排序均摊 O(N log N)实际常数很小。单纯从“通过题目”的角度看这无疑是最省事的方案。如果我在比赛中遇到类似的 Top K 题且没有算法训练要求我大概率会用库函数快速过掉把时间留给其他题目。但如果题目训练意图就是“请用归并排序”那调库函数就失去了练习意义。这也是为什么很多专题平台会专门强调“实现排序函数”或禁止直接调用排序 API。平时刷题可以用库函数加速理解训练基本功时还是建议徒手实现经典排序两种模式切换着来效率和积累都能兼顾。5.3 快速选择从“全排序”到“局部选择”若只想求前 M 大不求内部也有序快速选择算法可以做到期望 O(N)。思路借鉴快排的 partition一次划分后基准元素把数组分成两段一段大于基准一段小于基准。如果大段的长度刚好等于 M答案就在大段如果超过 M继续在大段里递归选择如果不足 M则从另一部分中再补足剩余数量。听起来很理想实现起来却比归并更容易写错partition 的边界、递归的出口、基准元素的选择都会影响正确性和最坏情况。当 M 较小时它可以成为性能最优解但当题目本身是“排序专题”时用快速选择多少有些跑题。我在实际做题时的倾向是训练归并就用归并现场救急再考虑快速选择。5.4 横向对比什么时候选哪种方案时间复杂度空间复杂度适合场景实现难度归并排序O(N log N)O(N)全排序训练分治中小顶堆O(N log M)O(M)M 远小于 N中快速排序系O(N log N) 均摊O(log N) 栈空间通用全排序低调库/ 中手写快速选择O(N) 期望O(log N) 栈空间只要前 M 大不要求有序高从应付“寻找大富翁”这道题来看归并排序是给分最稳、也最贴合专题意图的答案。它不像快速选择那样需要精确控制基准也不像堆那样对 M 的大小敏感只要把合并逻辑写对数据范围内基本不会超时。这也是我最终把归并排序作为主方案的原因。刷完这道题我最大的体会是归并排序的代码量不大难点全在“每一个下标都恰好落在它该在的位置”。合并前脑子里要有一幅双指针移动的画面合并后要记得把临时数组回写输出前先看一眼 M 和 N 的关系。把这些细节一次想清楚比提交十次去试错高效得多。最后分享一个小经验如果某次提交出现“排序结果只有前半段有序、后半段混乱”几乎可以断定是回写操作漏了或回写区间写错如果在本地测试没问题但 OJ 报内存类错误先把大数组挪到全局变量再说。把这几条记下来“寻找大富翁”这类归并排序专题题基本就稳了后面再遇到逆序对统计、链表归并排序也能顺藤摸瓜。

归并排序实战：用分治思想解决“寻找大富翁”Top M问题

相关推荐

python的机器人基础原理工业场景模拟第十九篇:机械臂仿真，零重力工况模拟，关闭重力项，输出仅由运动产生的关节力矩曲线。

TCP SACK乱序级别reordering：重传不高但吞吐上不去的真凶

# 多屏显示系统分辨率异常怎么办？EDID、刷新率与信号兼容性排查方法

更多资讯

51单片机流水灯实战教程

工业RFID如何落地智能制造产线：从频段原理到MES集成的技术拆解

ACE前台框架下载与工程化实践指南

Visual C++ 6.0 安装与最小化配置：Legacy 系统调试与逆向必备工具链

身体调理手法核心技术解析与行业现状

江西燃气发电机厂家推荐

今日更新

小波包能量谱原理与MATLAB实现：从频带分解到故障特征提取

基于LSTM的网易云音乐评论情感分析：数据清洗与模型调优实战

Alpha-Beta剪枝与极大极小值算法：博弈树搜索原理与实战优化

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？