企业官网建设流程全解析

在 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 和 1，1 先入列；再比较 4 和 5，4 入列；然后 7 入列，5 入列，得到[1, 4, 5, 7]。右侧类似地合并出[2, 3, 6, 8]，最后再把两个 4 元段合并成完整有序数组。

递归的出口就是 low == high，也就是区间里只有一个元素的时候。这时候什么都不用做，直接返回，因为单个元素必然有序。整个排序过程不需要额外来判断数组是否为空，只要在调用前保证 low <= high 即可。

2.2 合并过程的双指针，为什么要这么移动

合并是两个有序段变成一个有序段的过程。假设左右两段分别是wealth[low..mid]和wealth[mid+1..high]，我会用三个下标控制：i 指向左段当前位置，j 指向右段当前位置，k 指向辅助数组 temp 的写入位置。

每一步只做一件事：比较wealth[i]和wealth[j]。如果左边小，就把左边的数放进 temp，i 和 k 各前进一位；否则把右边的数放进 temp，j 和 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，加辅助数组约 8MB，OJ 通常给得了。但如果你在函数内部临时声明超大数组，可能导致栈溢出或运行时错误，所以这类题我一般建议把数组开成全局变量，这个细节在第 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 横向对比：什么时候选哪种

从应付“寻找大富翁”这道题来看，归并排序是给分最稳、也最贴合专题意图的答案。它不像快速选择那样需要精确控制基准，也不像堆那样对 M 的大小敏感，只要把合并逻辑写对，数据范围内基本不会超时。这也是我最终把归并排序作为主方案的原因。

刷完这道题，我最大的体会是：归并排序的代码量不大，难点全在“每一个下标都恰好落在它该在的位置”。合并前脑子里要有一幅双指针移动的画面，合并后要记得把临时数组回写；输出前先看一眼 M 和 N 的关系。把这些细节一次想清楚，比提交十次去试错高效得多。

最后分享一个小经验：如果某次提交出现“排序结果只有前半段有序、后半段混乱”，几乎可以断定是回写操作漏了或回写区间写错；如果在本地测试没问题但 OJ 报内存类错误，先把大数组挪到全局变量再说。把这几条记下来，“寻找大富翁”这类归并排序专题题基本就稳了，后面再遇到逆序对统计、链表归并排序，也能顺藤摸瓜。