企业官网建设流程全解析

做这套题时我最初的提交记录特别丢人——先写了个裸的sort直接交，数据量不大，过了，但我自己清楚，这种写法对“寻找大富翁”可以说毫无解释力。题目考的是排序，可你要真只会调库，那“归并排序”四个字就永远只是课本上的概念，不是手里能用的工具。后来我老老实实用归并排序重写了一遍，才发现这道看似人畜无害的题里藏着不少细节，从合并方向到临时数组的复用，每一个决定都影响你能不能写出干净、稳定、不超时的代码。

这篇就把我的完整实现思路、踩过的坑、以及在Top-M场景下不同排序方案的取舍整理出来。如果你正在刷PTA、准备数据结构考试，或者单纯想把归并排序吃透，这篇应该对你有用。

1. 题目背后真正要考的两件事

1.1 Top-M问题为什么不能只靠一个sort交差

“寻找大富翁”的题目描述很直白：给你N个人的财富值，让你输出排在前M位的那些数字。第一反应基本都是全排一遍然后取前M个，C++里sort，C里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 临时数组的复用：避免每层malloc

merge函数需要一个临时数组来承接合并结果。最差的写法是在每次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[mid+1..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]，右块范围是[mid+1, 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、堆、快选怎么选

我在这道题上实测过几种方案，也观察过不同数据规模下的表现。把这几种常见思路放在一张表里对比，会更清楚它们各自的适用边界。

先说sort。如果是单数据情况，直接sort全排再取前M个，代码最短，效率通常也能过。但你要知道这种做法在“只取前M”这件事上一点也不聪明：N=100万、M=10时，它把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]和[mid+1, right]两段。最容易犯的错是把第二段的左边界写成mid，也就是递归调用时写成了mergeSort(a, tmp, mid, right)。

这样写会造成什么结果？当区间长度为2时，比如left=0, right=1，mid=0，第二段递归变成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 逆序对计数

学完归并排序后，很多排序题会进阶到“统计数组中的逆序对数量”。逆序对的定义是：如果存在i<j但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个结果就是最后要保留的有序输出。归并排序从头到尾贯穿了这道题的价值，也贯穿了整个排序算法知识体系。

最后再分享一点个人体会：我后来在很多题目里都把归并排序当兜底方案用，因为它的复杂度不依赖输入数据分布，不会像快排一样在极端数据里翻车。这次为了写清楚“寻找大富翁”这道题，我又把这个基础算法认真重写了一遍，那些之前觉得“没必要深究”的比较方向和临时数组细节，在调试时全都变成了实打实的经验。如果你也正卡在某个排序题上，别急着看题解，先把手写归并跑通，你会感谢自己这个选择。