企业官网建设流程全解析

很多刷题同学第一眼看到“寻找大富翁”这个题目，大概率会愣一下：这跟那个经典桌游有什么关系？其实一点关系都没有。这里的“大富翁”指的是财富值最高的人，题目要你从一大堆财富数据里，把最有钱的那几位找出来，并且按照从大到小排好。

这道题看起来简单，真正动手写却很容易翻车。它默认你不仅会排序，还得知道不同排序算法的复杂度差异；它不要求你掌握什么高级数据结构，但如果你只会写冒泡排序，面对十万级、百万级的输入，基本就是等着超时。归并排序正是这类题目最经典的解法之一，也是理解“分治”思想绕不开的必修课。

这篇文章我会从题目本身的坑讲起，接着分析为什么归并排序适合出现在这里，再给你完整的递归版和迭代版实现，最后把输出前M大、数组越界、格式错误这些高频问题全部过一遍。适合正在学数据结构、准备期末上机、或者想在在线判题平台上稳定拿分的人。就算你平时习惯直接调用排序函数，这篇文章里的边界处理和调试思路也值得看一看。

1. 题目到底在考什么：先把需求拆干净

1.1 输入输出长什么样

大多数在线判题平台上出现的“寻找大富翁”，输入描述都大同小异。第一行给出两个正整数N和M，第二行给出N个整数，每个整数代表一个人的财富值。注意这里说的是“整数”，不是“正整数”，也就是说数据里可能出现负的财富值。输出要求在一行里给出最大的M个数，并且从大到小排列，数字之间用空格隔开。

不同题库的输入格式偶尔会有一点出入，比如有的题目N和M分两行给，有的把N个整数拆成多行输入，有的在N=1或M=0时还有特殊约定。核心模型是不变的：给你一个长度为N的数组，输出数组中前M大的元素，降序排列。我自己的习惯是，拿到题目先把输入输出样例手抄一遍，再开始想排序方案，不要急着敲代码。这样能少走很多弯路，也方便后面写测试数据。

1.2 数据规模才是真正的题目

排序类题目最难的部分往往不是排序本身，而是数据规模。N可能来到10^5甚至10^6，M可能很小，也可能接近N。当N是10^5时，O(N^2)的冒泡排序和选择排序大概率直接超时；归并排序这种O(N log N)级别的算法则能稳稳跑完。当N是10^6时，归并排序需要多开一个长度为N的辅助数组，按int类型算也就是4MB左右，内存完全能接受。

所以这道题表面是在让你做财富排名，实际是在考你对算法复杂度的敏感程度。很多人排序函数写得滚瓜烂熟，最后却在输出格式或者数组越界上栽跟头。这种时候不要怀疑自己的排序能力，先回去检查边界条件，往往问题就藏在那些不起眼的细节里。

1.3 一句话概括解题模型

读入N、M和N个整数，把数组排序成降序，然后输出第0个到第M-1个元素。如果M大于N，最多也只能输出N个，所以输出个数要用M和N里的较小值。如果M小于等于0，那就什么都不需要输出。理解了这一步，接下来的方案选型就好办了。

2. 方案选型：为什么归并排序能在这题里站住脚

2.1 先把主流排序拉出来对比

遇到排序题，脑子里至少要有一张复杂度对照表。我用表格把常见的几种排序捋一遍：

数据规模小的时候，冒泡排序写法最简单，但一旦N变大就会很痛苦。快速排序平均性能好，但最坏情况退化到O(N^2)，虽然随机化可以规避，理论上总让人不那么踏实。堆排序时间复杂度稳定且空间省，但实现起来容易在“堆化”环节出错，而且它不稳定。归并排序的优势在于：时间复杂度严格保证O(N log N)，不受输入数据顺序影响，稳定，实现思路又清晰，非常契合这种“训练基本功”的排序题。

2.2 归并排序的本质是合并两个有序序列

理解归并排序之前，先理解一个更小的问题：现在有两个已经排好序的数组，怎样把它们合并成一个更大的有序数组？做法很简单，各拿一个指针从头开始比，谁更大就先放进结果里，等于的情况随便取哪边，取完的结果依然是降序。归并排序就是不断把数组切成两半，直到每段只有一个元素，因为单个元素天然有序，然后再一层层向上合并。

这个过程很像两个人各自拿着一摞已经按牌面排好序的扑克牌，每一轮比较牌面大小，把更大的一张抽出来放到新牌堆里。最后一摞新牌自然就是整副牌的有序版本。我觉得这个类比比任何公式都直观，很多同学第一次听就能记住合并的流程。

2.3 什么时候可以不用归并

如果你是打比赛且允许调用现成库函数，直接用排序函数当然更省事。但这道题既然明确点名要归并排序，就老老实实手写一遍。手写归并的收获不只是AC一个题目，它的合并思想可以顺路解决求逆序数、合并两个有序链表、区间归并这类问题。以后你面试或者做项目时遇到“两个有序流合并”之类的需求，也会感谢当年认真写过的merge函数。

3. 归并排序实现：从递归到迭代的完整代码

3.1 公共的merge函数

merge函数是整个归并排序的心脏，建议单独抽出来写。下面这份代码默认按降序合并，也就是把大的元素往前放：

void merge(int a[], int l, int mid, int r, int tmp[]) { int i = l, j = mid + 1, k = 0; while (i <= mid && j <= r) { if (a[i] >= a[j]) { tmp[k++] = a[i++]; } else { tmp[k++] = a[j++]; } } while (i <= mid) tmp[k++] = a[i++]; while (j <= r) tmp[k++] = a[j++]; for (int t = 0; t < k; t++) { a[l + t] = tmp[t]; } }

这里要特别注意三点。第一，比较用的是>=而不是>，只有大于等于时取左边，这样值相等的元素能保持原有相对顺序，这就是稳定性的体现。第二，第一个while结束后，一定有一边还剩数据，后面两个while就是处理残余元素的。第三，合并结果必须先从tmp拷贝回a，因为下一次合并依赖的是a数组的状态，如果你只把结果留在tmp里，后面的排序就会乱套。这里的区间定义统一采用闭区间[l, r]，两边都能取到，不容易越界，我推荐一直用这种风格。

3.2 递归版归并排序

有了merge函数，递归版就非常清爽：

void mergeSort(int a[], int l, int r, int tmp[]) { if (l >= r) return; int mid = l + (r - l) / 2; mergeSort(a, l, mid, tmp); mergeSort(a, mid + 1, r, tmp); merge(a, l, mid, r, tmp); }

计算mid我习惯写l + (r - l) / 2，而不是(l + r) / 2。虽然N=10^5时两者都不会溢出，但这是一个值得培养的好习惯，以后遇到更大范围的题目就能避开整数溢出的坑。递归顺序就是标准的“分治三步”：先排左半边，再排右半边，最后合并。只要merge函数没问题，排序结果就一定是正确的。

递归深度大概是log2(N)，N是10^6时也只有二十层左右，基本不用怕爆栈。不过有些在线判题系统给的栈空间很小，或者同一套代码你还想拿去处理更大的数据范围，那迭代版就更有优势。

3.3 迭代版归并排序

迭代版也叫自底向上归并，不依赖递归栈。它从宽度为1的区间开始，把相邻的两个长度为width的有序区间合并成一个长度为2*width的有序区间，然后width不断翻倍，直到整个数组有序：

void mergeSortIter(int a[], int n, int tmp[]) { for (int width = 1; width < n; width *= 2) { for (int l = 0; l < n; l += 2 * width) { int mid = l + width - 1; int r = l + 2 * width - 1; if (mid >= n - 1) { continue; } if (r > n - 1) { r = n - 1; } merge(a, l, mid, r, tmp); } } }

为什么mid >= n - 1要直接跳过？因为左半区间已经到数组末尾了，右边根本不存在，没有可合并的对象。为什么r要裁剪成n - 1？因为最后一组可能凑不满2*width个元素，把右边界收到数组最后一位即可。迭代版的时间复杂度和递归版完全一致，只是省去了函数调用栈的开销。在栈空间紧张的时候，这一版能救命。

3.4 选择降序还是升序

题目要求从大到小输出，所以你必须在“合并时用降序”和“输出时倒序”里选一种。我建议直接在merge里按降序合并，这样排序完成后数组第一个元素就是最大的，输出前M个非常直接。如果你平时写习惯了升序，也不是不行，最后从a[n-1]倒着输出前M个就能得到从大到小的结果。最怕的是排序用降序、输出却当成升序取数，或者反之，这种方向上的混乱会让结果全错，还很难一眼看出来。

4. 完整解题流程：从读入到输出的每个细节

4.1 主函数框架

有了前面的合并和排序函数，主函数可以这样写：

#include <stdio.h> #include <stdlib.h> void merge(int a[], int l, int mid, int r, int tmp[]) { int i = l, j = mid + 1, k = 0; while (i <= mid && j <= r) { if (a[i] >= a[j]) { tmp[k++] = a[i++]; } else { tmp[k++] = a[j++]; } } while (i <= mid) tmp[k++] = a[i++]; while (j <= r) tmp[k++] = a[j++]; for (int t = 0; t < k; t++) { a[l + t] = tmp[t]; } } void mergeSort(int a[], int l, int r, int tmp[]) { if (l >= r) return; int mid = l + (r - l) / 2; mergeSort(a, l, mid, tmp); mergeSort(a, mid + 1, r, tmp); merge(a, l, mid, r, tmp); } int main(void) { int n, m; if (scanf("%d %d", &n, &m) != 2) return 0; int *a = (int*)malloc(n * sizeof(int)); int *tmp = (int*)malloc(n * sizeof(int)); if (a == NULL || tmp == NULL) return 0; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } mergeSort(a, 0, n - 1, tmp); int limit = m < n ? m : n; for (int i = 0; i < limit; i++) { if (i) printf(" "); printf("%d", a[i]); } printf("\n"); free(a); free(tmp); return 0; }

这个框架能覆盖大部分情况。limit = m < n ? m : n这句非常关键，它防止了M大于N时越界读取数组。你可能会觉得题目保证了M小于等于N，但写代码时做一层保护并不会损失什么，反而能让你的程序在面对边界数据时表现得更稳健。

4.2 动态数组还是定长数组

当N未知或者可能很大时，用malloc动态分配最稳妥。如果题目明确给出N最大不超过100000，直接开一个a[100005]也能过，但动态分配的写法更通用，换个题目就能直接用。有一点要注意：malloc可能失败，返回NULL，这时候继续往数组里写数据一定会段错误。虽然在线判题平台一般不会让你走到这一步，但检查一下指针总不是坏事。

4.3 格式输出是隐藏扣分点

这道题对输出格式的要求通常比较严格，最常见的要求是“最后一个数字后面没有空格”。很多同学喜欢这么写：

for (int i = 0; i < limit; i++) { printf("%d ", a[i]); }

在部分允许行末空格的题目里，这样能过。但“寻找大富翁”这类题目往往会检查你的输出格式，行末多一个空格轻则报格式错误，重则被当成答案错误。我的习惯是先输出第0个元素，然后从第1个开始每个前面加一个空格，也就是上面主函数里if(i) printf(" ");的写法。这样无论多少个元素，最后都不会有多余空格，也不会缺换行。

4.4 复杂度的结论

归并排序的时间复杂度是严格的O(N log N)，不随初始输入顺序变化。N=10^5时，这个量级的操作在绝大多数评测机器上只需要几十毫秒，时间完全够用。空间上除了输入数组a之外，额外需要一个和它等长的辅助数组tmp，所以总空间占用大约是2N个int。N=10^6时大概是8MB，一般内存限制都在可接受范围内。这也是我推荐归并排序的原因：性能可预期，资源开销清晰可控。

5. 常见问题与排查实录

5.1 问题一：段错误

段错误基本都是越界访问造成的。常见的场景有几种：

• merge函数里把右边界r算得太大，导致访问到数组外面；
• 递归边界写错，比如mergeSort(a, l, mid - 1)导致左右区间重叠甚至一直递归；
• 动态分配数组后，tmp没有分配同样大小，或者压根忘了分配。

排查这类问题，最简单的方法是先用极小的数据在本地跑，比如N=5，再打开内存检查工具跑一遍。段错误基本逃不出小数据测试这一关，很快就能定位到具体是哪个下标越了界。

5.2 问题二：合并后部分数据丢失

这是我见过最隐蔽的bug之一。合并时如果直接在a数组上做交换，很容易出现“覆盖了还没处理的元素”的情况。比如你一边用a[i]和a[j]比较，一边把比较结果写回a[i]，那后边的原始数据可能就被覆盖掉了。正确的做法一定是先把结果放进tmp，合并完再整体拷回a。症状也很典型：两个子数组各自排得好好的，一合并就发现某个数字凭空消失。遇到这种情况，不用怀疑数学问题，直接检查merge函数有没有正确使用tmp。

5.3 问题三：输出顺序反了

如果你merge时写的是升序，输出时却直接从a[0]开始打印，那打印出来的恰好是最小的M个数，和题目要求正好相反。这种情况特别容易发生在改代码的时候，改完排序方向忘了调整输出逻辑。我的排查习惯是打印一下排序后的整个数组，快速目测第一个元素是最大还是最小。也可以用一个一眼能看出的数据，比如1、5、3、9、2，正确降序结果应该是9、5、3、2、1，如果输出的是1、2、3、5、9，那不用犹豫，方向错了。

5.4 问题四：超时

如果用了归并排序还超时，大概率不是算法复杂度的问题，而是死循环或者输入输出拖慢。迭代版里有一个特别容易踩的坑：width是int类型，当n很大时，最后一轮width *= 2可能溢出变成负数，for循环判断width < n依然成立，于是程序永远在循环里转。解决办法是用width > n / 2提前跳出，或者把width声明成long long。还有一个常见原因是用C++的cin/cout却忘了关同步，数据量大时输入输出也会成为瓶颈，换成scanf/printf立竿见影。

5.5 问题五：判题结果格式错误

如果你百分百确定排序和取数都对，但平台反馈格式错误，那几乎可以肯定是行末空格或换行的问题。检查一下最后一项输出后有没有多余空格，最后一行的换行符号有没有输出。我自己习惯把所有输出生成到文件里，再和标准答案用文本比较工具逐字节比对，格式问题一眼就能暴露出来，比反复提交到评测系统高效得多。

6. 一些实战体会与小技巧

6.1 做题顺序建议

我建议你按“先写merge函数，再写递归版，再写迭代版”的顺序来练习。merge函数是基础，写对了递归版十分钟就能搞定；迭代版稍微绕一点，但理解了区间划分逻辑之后也就是多十行代码的事情。练习归并排序的时候，不要只追求AC，试着把递归版和迭代版都跑一遍小数据，再看一遍输出结果。这样你对“分治”的理解会比单纯背代码深很多。

6.2 归并排序还能用在哪儿

搞定这道题之后，merge函数别急着删。以后遇到求逆序数、合并有序链表、处理大文件外部排序等场景，核心逻辑都是同一个“合并两个有序序列”。我后来在做某个模拟项目时，需要把两个按时间戳排序的日志流合并成一份完整日志，直接就是把当年这个merge改了几行拿来用。归并排序真的很适合作为第一个真正吃透的排序算法，因为它能迁移的地方太多了。

6.3 一个关于稳定性的小细节

用>=还是>，对这道题来说不敏感，因为元素只是普通整数。但如果你把“财富值”换成“姓名+财富值”的复合结构，比如结构体里存了姓名和金额，并且希望金额相同的人维持输入顺序，那一定要用>=。这就是稳定排序的意义。花三分钟把这个细节想明白，以后遇到需要稳定排序的业务场景，你就不会写错比较符号。这也是归并排序比快速排序更适合这类题目的隐藏加分项。