PAT 乙级刷到 1035 这道题的时候我卡的时间比预想中长很多。题目本身不复杂——给一个初始序列再给一个排序算法执行到一半的中间序列让你判断这个中间态来自插入排序还是归并排序然后输出这个算法“再走一趟”之后的样子。真正容易出错的地方反而全在“中间序列”和“再走一趟”这两个词上。尤其是我第一次提交时样例全过最后一个测试点反复错最后才发现问题出在对归并排序“一趟”的理解上。这篇就围绕这题把完整解法、代码和实际踩过的坑都梳理一遍正在刷 PAT 乙级的同学可以对照着写想练“模拟排序过程”这类题的人同样值得看。1. 这道题的真正考点反推“中间状态”而不是比最终结果1.1 第一次读题时我理解错的地方我一开始把题目理解成“给定初始数组和最终有序数组判断能用插入排序还是归并排序排出来”然后陷入了一个很蠢的误区任何排序算法最终都会把数组变成同一个非降序序列怎么可能靠最终结果区分算法所以题目给的一定不是最终结果而是一张排序过程里的“快照”。这个快照就是某个排序算法在执行若干轮之后、还没执行完时数组的状态。你要做的是根据这张快照反推出它属于哪种排序然后继续往下模拟一轮输出下一张快照。这其实是一件很有意思的事插入排序和归并排序的每一步都有明确的“过程特征”我们就是在利用这些特征做反推。它不是要你真的去排序而是要你把两个算法的执行过程拆解得足够细细到能识别出“走到哪一步了”。1.2 两种排序算法中间状态的核心特征插排的中间状态有一个非常直观的特征数组前一部分是已经排好序的非降序列后一部分还保留着原始数组的相对顺序。因为插入排序每一轮只处理一个元素把它插到前面有序区的合适位置后面没碰过的元素一直保持原样。归并排序的中间状态特征完全不同数组会被切成一些长度相同的块每一块内部有序但块和块之间不一定有序。比如第一轮归并结束后每两个相邻元素是一组组内升序第二轮结束后每四个元素是一组组内升序。所以理论上只要抓住这两个特征就能大致判断出中间序列是谁的产物。但“大致判断”在 OJ 上是不够的因为边界条件一多特征判断就容易翻车。更稳的做法是直接模拟两个算法的每一轮拿模拟结果和给定的中间序列去比对谁对上了就是谁。2. 判断插入排序模拟法为主特征判断法作验证2.1 为什么逐轮模拟比“找断点”更可靠网上有不少题解会用一个更省事的判断方法从前往后找到第一个不满足非降序的位置 pos然后检查 target[pos..n-1] 是否和原始序列完全相同如果相同就认定是插入排序。这个思路本身没问题因为它就是利用“插排只处理前缀后缀保持原样”的特征。但我建议你在实际写代码时还是用逐轮模拟。原因有两个第一模拟的思路是线性的不容易漏判第二它不依赖“特征法”里那些看似成立、实际容易踩空的推导。比如完全有序的序列会让断点法直接走到末尾这种边角情况就容易让人心里没底。模拟法从原始序列开始每一轮插一个元素然后和目标数组比对逻辑非常朴素反而是最不容易错的。而且 N 不超过 100模拟法的时间开销完全可以忽略。在考试环境下选择“代码长但思路简单”的方案往往比“代码短但需要时刻提防边界”的方案更划算。2.2 插入排序匹配后如何输出“下一步”模拟插入排序的代码骨架是这样的先把原始序列拷到 work 数组然后从 i 1 开始循环把 work[i] 插入到 work[0..i-1] 的正确位置。每次插入完成后判断 work 是否等于 target。如果相等说明当前轮次就是中间序列对应的状态接下来要做的就非常明确继续把 work[i1] 这个元素插入到前面有序区然后把结果输出。这里有个细节值得单独说插入排序的“下一步”完全可能不改变数组内容。比如目标数组已经是前三个有序第四个元素恰好也大于前三个里的最大值那插入它时数组不会变。这是合法输出不要觉得代码没跑对。我在这道题的代码里特别注释了一行// 测试数据保证存在下一步i 1 n 恒成立如果匹配发生在最后一轮即 i n - 1 时目标序列已经完成全部插入此时“下一步”不存在。题目不会给这种数据但知道这个边界能帮你在读题时更安心。3. 归并排序模拟gap 翻倍合并的全过程与边界处理3.1 为什么必须用自底向上的迭代版本这是整道题最大的坑。归并排序有两种理解方式递归版本和自底向上的迭代版本。递归版本会产生一个非常自然的“中间状态”——比如左半部分已经排完序右半部分还没处理但这是递归执行到某次调用返回时的状态。而 PAT 这道题里的“每一趟归并”指的是对整个数组按当前段长进行两两归并的结果也就是自底向上的迭代过程。我最初就栽在这里。我试图用递归归并的调用顺序去模拟每一层的中间状态结果在部分测试用例上怎么都比对不上。原因很简单n 4 时自底向上第一轮 gap 1结果是相邻两两有序而递归版本先处理左半再处理右半中间状态出现的时间点完全不同。所以结论非常明确这题必须用自底向上迭代模拟gap 从 1 开始每轮结束翻倍直到 gap n。3.2 合并实现里的两个致命细节第一个细节是临时数组的覆盖。每轮归并会把两个有序段合并到 tmpArr 的对应区间里但有些组可能只有一段比如数组长度为奇数或者末尾剩下的元素不够一个完整段。这时候很多人会顺手跳过这段的拷贝但这就埋了一个雷tmpArr 对应位置存的是上一轮留下的旧值等后面整体拷贝回 work 时那一小段就变成了残留数据污染。正确做法是哪怕只有一个段也要把这段原样拷贝到 tmpArr 的对应位置。合并的代码可以这样写int p l, q m, idx l; while (p m q r) { if (work[p] work[q]) tmpArr[idx] work[p]; else tmpArr[idx] work[q]; } while (p m) tmpArr[idx] work[p]; while (q r) tmpArr[idx] work[q];第二个细节是匹配和输出的关系。归并模拟中每一轮结束后先判断“之前是否已经匹配过”如果匹配过就直接输出本轮结果并返回否则再判断当前数组是否等于目标序列。这个顺序很重要它的逻辑是找到目标那一轮之后gap 还要再翻倍执行一轮那才是题目要求的“下一步”。如果先判断当前轮是否等于目标再判断是否匹配过反而可能在目标连续两轮都相同的情况下多走一轮。gap 的停止条件是 gap n因为当 gap 超过数组长度的一半后下一轮其实就是把整个数组归并成完全有序再往下就不需要了。比如 n 6gap 依次取 1、2、4三轮结束n 5gap 取 1、2、4最后一轮把前四个和最后一个合并。4. 可以直接跑过的完整代码4.1 整体结构代码我分成三部分工具函数equal 和 printArray、插入排序模拟函数、归并排序模拟函数。主流程先调用插入排序模拟如果返回 false 再调用归并模拟。这样逻辑非常清楚调试时也方便单独验证某一段。注意模拟前一定要把原始序列拷贝到 work 数组不要在 origin 上直接操作否则后续归并模拟还需要原始数据就被上一次模拟改掉了。这个问题我在第一次写的时候就踩过建议特别留意。4.2 完整代码#include cstdio #include algorithm using namespace std; const int MAXN 105; int n; int origin[MAXN], target[MAXN], work[MAXN], tmpArr[MAXN]; bool equal(int a[], int b[]) { for (int i 0; i n; i) { if (a[i] ! b[i]) return false; } return true; } void printArray(int a[]) { for (int i 0; i n; i) { if (i) printf( ); printf(%d, a[i]); } printf(\n); } bool solveInsertion() { for (int i 0; i n; i) work[i] origin[i]; for (int i 1; i n; i) { int key work[i]; int j i - 1; while (j 0 work[j] key) { work[j 1] work[j]; j--; } work[j 1] key; if (equal(work, target)) { printf(Insertion Sort\n); // 测试数据保证存在下一步i 1 n 恒成立 int key2 work[i 1]; int k i; while (k 0 work[k] key2) { work[k 1] work[k]; k--; } work[k 1] key2; printArray(work); return true; } } return false; } void solveMerge() { for (int i 0; i n; i) work[i] origin[i]; bool matched false; for (int gap 1; gap n; gap * 2) { for (int i 0; i n; i 2 * gap) { int l i; int m min(i gap, n); int r min(i 2 * gap, n); if (m r) { for (int k l; k r; k) tmpArr[k] work[k]; } else { int p l, q m, idx l; while (p m q r) { if (work[p] work[q]) tmpArr[idx] work[p]; else tmpArr[idx] work[q]; } while (p m) tmpArr[idx] work[p]; while (q r) tmpArr[idx] work[q]; } } for (int i 0; i n; i) work[i] tmpArr[i]; if (matched) { printf(Merge Sort\n); printArray(work); return; } if (equal(work, target)) { matched true; } } } int main() { scanf(%d, n); for (int i 0; i n; i) scanf(%d, origin[i]); for (int i 0; i n; i) scanf(%d, target[i]); if (!solveInsertion()) { solveMerge(); } return 0; }4.3 代码里的几个细节解释solveInsertion 中匹配后我再对 work[i1] 做一次插入而不是直接对已经匹配的数组做某种“通用下一步”操作。原因在于插排的“下一步”就是处理下一个未排序元素位置非常明确。归并部分则不一样归并的“下一步”不是针对某个具体位置而是整个 gap 翻倍后的新一轮合并所以用 matched 标志控制输出时机。输出函数统一处理了行尾空格问题第一个元素前不打空格之后每个元素前打一个空格。PAT 对行尾空格很严格宁可多写几行判断也不要偷懒直接遍历输出导致最后一个元素后面多一个空格。5. 我实际踩过的三个坑5.1 递归归并和自底向上归并的中间序列完全不同这个坑在 3.1 里已经提到过但值得再展开一次。n 4 时如果原始数组是 [4, 3, 2, 1]递归归并先把左半 [4, 3] 排成 [3, 4]此时数组变成 [3, 4, 2, 1]而自底向上第一轮 gap 1 会同时处理两个组得到 [3, 4, 1, 2]。虽然递归版本下一步也可能出现 [3, 4, 1, 2]但两种模拟过程的“每一轮状态”在顺序上并不同步。如果用递归版本去比对目标序列就可能出现两种情况要么永远匹配不上要么碰巧匹配上了但你不敢确定是不是正确路径。我后来放弃递归思路一切以自底向上为准整个代码清爽了很多。5.2 临时数组残留值导致的“玄学错误”我最早一版归并代码里遇到末尾单段就直接跳过了没有拷贝。结果出现了一个很诡异的现象在某些长度的数组上中间几个数字莫名其妙地变成上一轮的值。排查了很久才发现tmpArr 里没有写这轮数据的区域还残留着上一轮结果整体拷贝回 work 时把旧数据带了进来。这种问题非常隐蔽因为数组稍微长一点或者数据本身没有明显规律时肉眼很难看出来。修法就是我在 3.2 里反复强调的所有区间不管有没有后半段都要确保 tmpArr 对应位置被正确更新。要么统一用合并逻辑要么单独拷贝单段。5.3 输出格式和“下一步不变”的处理PAT 对输出格式的检查相当严格第二行输出序列时每个数字之间用一个空格分隔行末不能有空格。我最早用了一个“每输出一个数字就加空格”的写法导致最后一个元素后面也带了空格提交直接提示格式错误。这个还好改真正让我犹豫的是另一种情况插入排序的下一步结果和当前中间序列完全一样。当时我以为是匹配逻辑写错了检查了好几遍才发现下一个待插入元素已经处于正确位置数组自然不变。这种情况并不多见但真遇到时不要慌直接输出相同序列就是正确答案。5.4 相等元素对模拟的影响题目里的数字不一定互不相同所以在插入排序和归并排序的模拟中比较符号要特别注意。插入排序里 while 条件用work[j] key而不是归并合并时用work[p] work[q]而不是。这样写能保持稳定排序的行为也避免因为等号处理不同而在某些边界数据上出现偏差。虽然从最终数组状态看等号怎么选往往不影响结果但在模拟题的语境下尽量和标准算法的稳定版本保持一致是最稳妥的选择。6. 几组边界用例自测全对才算真正掌握6.1 用例一奇数长度下的归并匹配5 5 4 3 2 1 4 5 2 3 1这里原始数组经过 gap 1 的归并轮后变成 [4, 5, 2, 3, 1]和目标一致。下一步 gap 2合并前两个有序对得到 [2, 3, 4, 5, 1]末尾的 1 单独保留。期望输出Merge Sort 2 3 4 5 1这组数据专门检验“末尾单段是否正确拷贝”的问题。如果你的临时数组处理有问题这里很容易出错。6.2 用例二重复元素下的插入排序匹配6 3 1 2 1 5 4 1 2 3 1 5 4插排模拟第一轮插入 1 得到 [1, 3, 2, 1, 5, 4]第二轮插入 2 得到 [1, 2, 3, 1, 5, 4]正好匹配。下一步插入下标为 3 的 1结果是 [1, 1, 2, 3, 5, 4]。期望输出Insertion Sort 1 1 2 3 5 4这组数据验证的是当数组里有重复数字时插入排序的后缀判断和下一步输出仍然正确。6.3 用例三最简单的归并匹配4 4 3 2 1 3 4 1 2gap 1 后得到 [3, 4, 1, 2]匹配目标。下一步 gap 2 时整个数组合并成 [1, 2, 3, 4]。期望输出Merge Sort 1 2 3 4这是我用来快速验证主流程是否正确的第一组数据简单直接。6.4 用例四插入排序“下一步不变”的特殊情形5 3 1 8 2 5 1 3 8 2 5插排第一轮插入 1数组变成 [1, 3, 8, 2, 5]恰好等于目标。下一步要插入下标为 2 的元素 8但 8 已经大于前面的 3插入后数组还是 [1, 3, 8, 2, 5]。期望输出Insertion Sort 1 3 8 2 5看到输出和输入一样时先别急着怀疑代码这是完全合法的结果。这类边界情况在 OJ 数据里不一定出现但自己想明白之后遇到类似情况就不会慌。这题做完之后我养成一个习惯凡是题目里带“中间序列”“下一步”这种说法的排序题都老老实实写模拟不靠特征推断走捷径。模拟代码虽然比“找断点”多几行但它把每一步都摆在你面前输出结果自然有依据。之后再遇到判断排序类型、输出迭代过程的题你也可以试试这个套路。