企业官网建设流程全解析

PAT 乙级 1035 这道题，在备考程序设计能力测试的人里应该算是个“磨人的小妖精”。题面本身很好懂：给你一个初始序列，再给你一个排序到一半的中间序列，让你判断这个中间序列到底是插入排序排出来的，还是归并排序排出来的，然后输出下一步排序的结果。听起来简单，但我当年第一次做的时候，一口气错了七八次，问题全出在“怎么判断”和“怎么输出下一步”这两个细节上。这篇文章就把这道题从原理到代码彻底掰开揉碎，适合正在刷 PAT 乙级、准备复试机试，或者想把插入排序和归并排序真正吃透的读者。

1. 题目到底在问什么：状态识别与下一步推导

1.1 题面拆解与核心考点

这道题的输入有三部分：第一个数是序列长度 n，第二行是原始未排序的序列 a，第三行是某个排序算法执行到一半的中间序列 b。要求输出两行，第一行是Insertion Sort或者Merge Sort，第二行是下一步继续排序后的结果序列。

核心考点其实不是排序本身，而是“状态识别”。你拿到一个中间序列，得能反推出它正在经历哪个算法的哪一轮。这一步想清楚了，后面输出下一步就只是顺水推舟。大多数人的出错点也就在这里：插入排序和归并排序在中间状态上长得有点像，尤其是排序轮次比较靠后的时候，光用肉眼很难区分。

1.2 这两个排序的中间状态有本质区别

插入排序的特点是，每一轮迭代只保证“前 k 个元素”有序，后面的元素一动不动，和原始序列完全相同。也就是说，它的中间状态一定可以分成两段：前一段是有序的，后一段是原封不动的原始序列。

归并排序就不一样了。自底向上的归并排序，每一轮会把整个数组切成若干等长的块，每个块内部排好序。因为涉及多个块的位置交换和内部重排，整个序列的后半段通常也不在原位。换句话说，归并排序的中间状态几乎处处都动过。

这个本质区别就是整道题的突破口。你只要找到一个分界点，看看分界点后面的元素是不是和原始序列完全一致，就能判断出到底是哪种排序。

2. 排序过程回顾：两种算法的“中间状态”长什么样

2.1 插入排序：像打牌时理牌

插入排序的原理大家应该都熟：从第二个元素开始，每次把当前元素往前面已经有序的序列里插，插到合适的位置。每轮结束后，前 i+1 个元素就是有序的。

举个例子，原始序列是3 1 2 8 7 5 9 4 6 0，第一轮把 1 插入到 3 前面，得到1 3 2 8 7 5 9 4 6 0。第二轮把 2 插到 1 和 3 之间，得到1 2 3 8 7 5 9 4 6 0。注意观察，每一轮过后，后面8 7 5 9 4 6 0这段完全没动过，和原始序列一模一样。这就是插入排序中间状态最明显的特征。

这里有个容易忽略的细节：如果当前要插入的元素已经在正确位置，比如1 2 3 8 7中把 8 往前插，它比 3 大，位置不用变，那么这一轮结束后序列和上一轮完全相同。这在做题时不影响正确性，因为比较相等序列时自然会匹配到那一轮。

2.2 归并排序：迭代写法才符合本题语境

归并排序有递归写法和迭代写法。递归写法是“先拆到底再往上合”，迭代写法是“从长度为 1 的有序段开始，两两合并”。这道题里的中间状态，实际上对应的是迭代写法。

迭代归并的每一轮，可以理解为用一个不断翻倍的块长去扫描数组：第一轮块长 2，把每两个元素排好序；第二轮块长 4，把每四个元素排好序；第三轮块长 8，以此类推。最后一轮如果剩余的元素不足一个块，就处理剩余的部分。

还是用上面那个原始序列，第一轮块长 2 的结果是1 3 2 8 5 7 4 9 0 6。可以看到，不仅前两个元素变了，后面7 5变成5 7，4 6变成0 6，后面六个数全和原序列不一样了。这就是归并排序和插入排序中间状态最直观的差别。

2.3 中间状态对比：一张表说清楚

理解了这两张“脸”，判断算法就简单了：在中间序列里从左往右找到第一个下降点（前一个比后一个大），如果下降点后面的所有元素和原始序列对应位置完全相同，这就是插入排序；否则就是归并排序。这是这道题最经典的特征判断思路，代码很短，但有一些边界坑，下面详细说。

3. 两种判断方案：特征判断法和模拟法

3.1 特征判断法：思路巧妙，但要小心边界

所谓的特征判断法，就是利用上面说的中间状态特征来判断。具体步骤是：先遍历中间序列 b，找到第一个满足b[i] > b[i+1]的下标 i，然后比较a[i+1]到a[n-1]这一段和b[i+1]到b[n-1]这一段是否完全相同。如果相同，说明从 i+1 开始后面都没动过，是插入排序；否则是归并排序。

如果是插入排序，下一步就是对 b 的[0, i+1]区间排序。因为当前前 i+1 个元素已经有序，下一个待插入的元素正是b[i+1]，把它插进去的效果等于把前 i+2 个元素整体排序。

这个方法写出来非常短，网上大部分题解也是这么写的。但它有两个暗坑：

第一，如果中间序列本身已经完全有序，就找不到b[i] > b[i+1]这个下降点，i 会落在序列末尾，代码会陷入尴尬的边界局面。虽然 PAT 的数据很少会出这种情况，但万一遇到，特征判断法就要额外处理。

第二，比较后半段是否相同的时候，用的是“后半段完全没动过”这个条件，这个条件在元素有重复值时依然成立，但要留意比较的是整个后缀而不是局部。我第一次写的时候，只比对了下降点后一个元素，结果连续报错，后来才发现应该比对整个后缀。

3.2 模拟法：代码长一点，但最稳

我个人更推荐模拟法，这也是我踩过几次坑之后才总结出来的经验。模拟法的思路非常简单粗暴：从原始序列 a 出发，老老实实地用插入排序和归并排序各跑一遍，每一轮得到一个中间状态，拿这个状态和 b 比对。一旦相等，就说明当前是哪种排序，并且再往后执行一轮，把那个结果输出即可。

这个方法看起来笨，但它有一个不可替代的优势：不需要分析任何边界特征，也不会出现“完全有序时无法判断”的死局。你只需要保证两个排序模拟过程本身是对的，判断逻辑就是顺带完成的。对于 n 不超过 100 的 PAT 乙级题目，时间复杂度完全不是问题，没必要为了省那点运行时间跟边界条件较劲。

模拟法的另一个好处是，找到匹配轮次后，下一步的结果可以直接复用排序代码生成，不用额外推导“下一步该对哪段排序”。这对考场上心态不稳、容易手抖的情况非常友好。

3.3 为什么用 sort 分块模拟归并是合法的

写归并排序模拟的时候，很多初学者会纠结一个问题：如果我用sort对每个块排序，而不是严格地两两合并，算不算作弊？会不会输出结果和真题要求不一致？

答案是不会。归并排序自底向上的每一轮，本质上是把相邻的两个“有序段”合并成一个更大的有序段。如果两个段各自有序，那么“合并后再排序”的结果，和“直接把整块用 sort 排序”的结果是完全一样的。所以用sort对每个块排序，等效于标准归并排序的一轮迭代。PAT 判题只检查输出序列，不检查算法过程的内部细节，用 sort 模拟归并完全合法。

这个“等效替换”的思路在考试里很常见：只要最终序列的生成过程和题目要求的排序逻辑等价，过程用什么方式实现并不重要。前提是你得能说清楚为什么等价，不然调试的时候思路容易混乱。

4. 完整代码实现与逐段讲解

4.1 C++ 版完整代码

直接给出我调试通过的完整代码，后面分几段讲解关键点：

#include <cstdio> #include <vector> #include <algorithm> using namespace std; int n; vector<int> a, b; void printResult(const char* type, const vector<int>& v) { printf("%s\n", type); for (int i = 0; i < n; i++) { if (i) printf(" "); printf("%d", v[i]); } printf("\n"); } bool simulateInsertion() { vector<int> t = a; for (int i = 1; i < n; i++) { int key = t[i]; int j = i - 1; while (j >= 0 && t[j] > key) { t[j + 1] = t[j]; j--; } t[j + 1] = key; if (t == b) { if (i + 1 < n) { int nextKey = t[i + 1]; int k = i; while (k >= 0 && t[k] > nextKey) { t[k + 1] = t[k]; k--; } t[k + 1] = nextKey; } printResult("Insertion Sort", t); return true; } } return false; } bool simulateMerge() { vector<int> t = a; for (int step = 2; step / 2 < n; step *= 2) { for (int i = 0; i < n; i += step) { int right = i + step; if (right > n) right = n; sort(t.begin() + i, t.begin() + right); } if (t == b) { int nextStep = step * 2; for (int i = 0; i < n; i += nextStep) { int right = i + nextStep; if (right > n) right = n; sort(t.begin() + i, t.begin() + right); } printResult("Merge Sort", t); return true; } } return false; } int main() { scanf("%d", &n); a.resize(n); b.resize(n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 0; i < n; i++) scanf("%d", &b[i]); if (!simulateInsertion()) { simulateMerge(); } return 0; }

这段代码的核心逻辑是：先模拟插入排序，每一轮生成中间状态后与 b 比较，如果相同就输出插入排序的下一轮；如果插入排序从头到尾没有匹配上，再模拟归并排序，逻辑完全相同。

4.2 插入排序模拟的细节：下一轮怎么生成

插入排序的模拟里，每一轮做的事情是：取出当前下标 i 的元素 key，把它往前插到合适位置。如果这一轮的中间状态恰好等于 b，说明 b 对应的是第 i 轮的结果，下一步要执行第 i+1 轮。

代码里下一个轮次的处理是直接取t[i + 1]接着插。这里有一个边界问题：如果i + 1已经等于 n，说明整个序列已经全部有序，没有“下一步”可言了。真题数据一般不会出现这种情况，因为题目要求必须能输出下一步。但写代码时最好加上if (i + 1 < n)的判断，避免数组越界导致运行时错误。这个防御性判断在考试里非常重要，就算数据不会触发，多写一行也不会扣分。

还有一个小细节：插入排序的循环变量从 1 开始，因为第 0 个元素本身就是一个长度为 1 的有序序列，不需要插入。这一点初学者经常搞错，导致模拟出来的第一轮状态和标准插入排序不一致。

4.3 归并排序模拟的细节：轮次边界是最容易错的地方

归并排序的模拟里，最关键的代码是循环条件for (int step = 2; step / 2 < n; step *= 2)。这个条件写得很小心，我最初写的是step <= n，结果在 n 等于 10 的时候漏掉了最后一轮整体合并，折腾了很久才发现。

原因在于，自底向上归并排序的轮次代表的是“合并两个长度为 step/2 的有序段”，所以 step 是当前合并后块的长度。当 step 还小于 2n 的时候，都存在一个“把整个数组合并成一个有序段”的潜在下一轮，只不过这个下一轮可能最终的块长度等于或大于 n。举个例子，n 等于 10 时，step 会依次取 2、4、8、16。step 取 16 的时候，实际上是把前 8 个有序元素和最后两个有序元素合并成整个数组的有序序列，这一步不能漏掉。

我不知道还有多少人在这一步上卡过。无论是原题还是同类模拟题，轮次边界都是最常见的失分点，所以我把这个坑单独拎出来强调一下。

另一个细节是，每次对块排序时，块的右边界要用min(i + step, n)截断，防止访问越界。C++ 的sort排序区间是左闭右开，所以sort(t.begin() + i, t.begin() + right)排序的是从 i 到 right-1 的元素。如果 right 超过了 n，就必须拉回到 n，不然 vector 下标越界会直接崩溃。

5. 常见问题与调试实录

5.1 归并排序总差一步：问题多半出在轮次边界

网上很多题解在模拟归并时用的是for (step = 2; step <= n; step *= 2)，这种写法在 n 为 2 的整数次幂时没问题，但对 n 等于 6、10、12 这类数字，最后一轮把整个数组归并成有序序列的步骤会被漏掉。

我调试时遇到的一个具体案例是：n 等于 10，b 恰好是归并排序最后一轮之后的结果，也就是整个数组已经完全有序。用错误的循环条件模拟时，程序从头到尾都匹配不上 b，于是走不到归并排序的输出逻辑，最后把插入排序的结果输出出去，导致答案错误。

排查方法很简单：自己手工算一下 n 等于 10 的时候，归并排序到底需要几轮，分别在 step 等于多少时执行。算完你就会发现，即使 step 已经大于 n，只要 step/2 还小于 n，那一轮就必须执行。把这些边界情况记住了，以后写任何归并模拟都不会再出错。

5.2 插入排序直接匹配到了“从没动过”的状态

还有一种情况容易迷惑人：如果 b 和原始序列 a 完全一样，插入排序模拟从第一轮开始比较时，每轮生成的状态都可能不等于 b，但归并排序模拟到某些轮次也不会等于 b，程序会陷入“两种算法都匹配不上”的困境。

严格来说，b 等于 a 意味着排序还没有开始执行任何一轮，这时你很难判断它是插入排序还是归并排序的第 0 轮。好在 PAT 的测试数据通常不会出现这种情况，因为题目明确要求输出下一步，第 0 轮状态对两种算法来说都没有唯一的下一步。如果真在考试里碰到，我的建议是直接按插入排序处理，因为在很多人的代码里，插入排序模拟会在第一轮生成一个不同于 a 的序列，不会误匹配，而归并排序第一轮生成的序列也不等于 a。真正需要担心的反而是那些“排序过程中序列没发生变化”的轮次，比如插入排序插入一个已经在正确位置的元素。

这类状态识别的问题，靠背题是不够的，建议自己构造几组包含重复元素、且排序轮次推进后序列不改变的测试数据，把代码跑一遍，感受一下匹配过程。跑过之后你就明白为什么模拟法在这种模糊状态下依然能稳定工作了。

5.3 输出格式和测试用例构造

PAT 对输出格式的要求非常严格，序列输出的行尾不能有多余空格，否则会被判格式错误。我最早写输出逻辑的时候，习惯性地在每两个数字之间加空格，最后一位后面也加了一个，结果交上去三次都是 Presentation Error。后来改成用一个标志位或者三目运算符控制空格，才彻底解决。

构造测试用例也有技巧。想验证插入排序判断，就手动执行两三轮插入排序，把中间结果当 b；想验证归并排序判断，就手动执行一两轮分块排序。我常用的自测数据是n = 10的3 1 2 8 7 5 9 4 6 0，因为这个序列乱序程度高、长度适中，插入排序和归并排序的第一轮结果差异非常明显，特别适合肉眼比对输出对不对。

还有一个更省事的方法：直接把你自己代码的输出拿去和其他通过代码的输出对拍。把 n 从 1 到 100，随机生成序列，随机执行若干轮插入或归并，生成大量中间状态，然后对比两份代码的结果。对拍几百组数据之后，如果还有边界问题，一定会暴露出来。

6. 写在最后的调试心得

这道题刷完，我最大的感受是：PAT 乙级真正考的不是你会不会写排序算法，而是你能不能理解一个算法执行到一半时，系统状态长什么样。我见过不少人能默写快排、堆排，却在这道题上反复卡壳，就是因为平时排序都是“一把梭”排完整，从来没有停下来观察过中间过程。建议你做完 1035 之后，自己把插入排序和归并排序的每一轮中间状态都打印出来，对着原始序列看一遍，那种直观印象比背十篇题解都管用。

另外，考场时间有限，能用暴力模拟就不要炫技。特征判断法虽然代码短，但前提是你对所有边界情况都门儿清；模拟法代码长一点，但思路直白，调试成本低，容错率高。我第一次考这类题时总想用最巧妙的解法，结果往往是在边界条件上来回折腾，浪费时间。后来学乖了，先保证一个稳妥的解法能跑通，再做优化，心里踏实很多。