1. 从一道判题说起为什么“插入排序还是归并排序”值得单独拎出来讲“7-273 插入排序还是归并排序 (25 分)”这个标题第一次看到的人大概率会愣一下排序算法我熟插入排序、归并排序都是教科书级别的老面孔可“判断某段中间序列到底来自哪种排序”这件事为什么能单独成题还值 25 分我当年第一次刷到这类题时也犯嘀咕直到自己动手把两种排序的“中间过程”逐帧打印出来对比才意识到这题考的根本不是“会不会写排序”而是你对排序过程的理解到底停留在结果层还是深入到了过程层。先把题目场景说清楚。典型的题面是这样的给定一个长度为 N 的初始序列再给定一个“中间序列”也就是某一步排序后得到的序列要求你判断这个中间序列是由插入排序产生的还是由归并排序产生的并输出下一步迭代后的结果。如果两种排序在某一步恰好得到相同的序列题目通常约定优先判定为插入排序。这个约定不是随便定的后面会详细讲为什么。这道题能解决什么问题它逼着你去回答一个非常本质的问题同样是“部分有序”的中间状态插入排序和归并排序留下的“指纹”是不一样的。插入排序的特点是“前缀有序、后缀原封不动”归并排序的特点是“若干个长度递增的有序段拼接”。抓住这两个指纹判断就变成了模式识别而不是真的去模拟两遍排序再比对——当然模拟两遍也能过但那是另一种思路各有取舍。适合谁来参考我觉得有三类人特别值得花时间啃透这题。第一类是正在准备算法类上机考试的同学这类“过程判断题”是高频考点考的是对算法执行轨迹的敏感度。第二类是已经工作、但想回头补一补算法基本功的开发者平时写业务代码调个sort()就完事了真让你说清楚底层每一步发生了什么未必讲得利索。第三类是带课或做辅导的人这题是个极好的教学素材能把“算法过程可视化”这件事讲得非常具体。我下面会从整体思路、两种排序的指纹特征、完整实操流程、常见坑与排查四个大块展开中间穿插我踩过的坑和实测有效的技巧。代码用 C 写因为这类题的输入输出格式和 STL 容器配合起来最顺手但思路是语言无关的你用 Python 或 Java 照样能套。2. 整体思路拆解为什么“识别指纹”比“模拟排序”更聪明2.1 两种排序的中间状态到底差在哪要判断一个中间序列来自哪种排序最直接的办法当然是拿初始序列分别跑一遍插入排序和归并排序每一步都记录快照然后拿给定的中间序列去比对谁先匹配上就是谁。这个思路绝对正确也绝对能过但它的代价是你要完整实现两套排序并且维护所有中间状态代码量大、容易写错而且一旦题目数据规模上去模拟的开销也不小。更聪明的做法是直接识别中间序列的结构特征也就是我前面说的“指纹”。我们分别来看。插入排序的执行逻辑是把序列分成“已排序区”和“未排序区”初始时已排序区只有第一个元素然后每次从未排序区取第一个元素插入到已排序区的正确位置。关键点来了——在任意一步中间状态已排序区永远是原序列的一个前缀而且这个前缀是升序的未排序区则完全保持原样一个元素都没动过。这就是插入排序最鲜明的指纹前缀有序后缀原封不动。归并排序这里指自底向上的迭代版本也是这类题默认的版本的执行逻辑是先两两合并长度为 1 的段得到若干长度 2 的有序段再两两合并长度 2 的段得到若干长度 4 的有序段以此类推直到整个序列有序。所以它的中间状态指纹是序列被切成若干个有序段每段的长度是 2 的幂次最后一段可能不满而且这些段是连续拼接的。把这两个指纹摆在一起判断逻辑就非常清晰了。给定中间序列先检查它是不是“前缀有序、后缀原样”——如果是那它极可能来自插入排序如果不是再检查它是不是“若干个 2 的幂次长度有序段拼接”——如果是那就是归并排序。提示这里的“前缀有序”判断有个细节不是要求整个前缀严格递增而是要求前缀部分恰好是初始序列前若干元素排序后的结果。换句话说你要验证的是“初始序列的前 k 个元素排序后是否等于中间序列的前 k 个元素”而不是简单看中间序列前 k 个是不是升序。这个区别是很多人第一次做这题时栽跟头的地方。2.2 为什么题目约定“相同时优先判插入排序”这个约定乍看像是出题人偷懒其实有它的道理。考虑一个极端情况初始序列本身就已经有序了。这时候插入排序的“第一步”之后序列不变归并排序的“第一步”之后序列也不变两者完全重合。如果不做约定判题就没法给出唯一答案。那为什么优先判插入排序而不是归并排序我的理解是从“最小改动”的角度看插入排序在已有序序列上的表现更“自然”——它本来就不需要做任何实质性的移动。而且从实现角度插入排序的指纹检查前缀有序比归并排序的指纹检查2 的幂次分段更简单先检查简单的、命中率高的符合工程上的“短路原则”。这个约定你在写代码时必须严格遵守否则测试点里那些“两序重合”的用例会直接把你卡死。2.3 两种思路的取舍模拟 vs 指纹我把两种思路的对比整理成表格方便你根据场景选择。对比维度模拟排序法指纹识别法核心逻辑跑两遍排序逐步比对快照直接检查中间序列的结构特征代码量大需实现两套排序快照管理小主要是特征判断逻辑时间复杂度O(N² log N) 级别含快照比对O(N log N) 或 O(N²)取决于实现出错概率高快照边界容易搞错中指纹判断的边界要小心适用场景想彻底理解排序过程时应试、追求代码简洁时可扩展性差换一种排序就要重写好加新排序只需加新指纹我个人的建议是第一次做这题时用模拟法把两种排序的每一步都打印出来看建立直觉之后再用指纹法重写一遍体会两种思路的差异。这个学习路径比直接抄指纹法答案有价值得多。3. 核心细节解析指纹判断的每一步都要抠清楚3.1 插入排序指纹的精确判断方法插入排序的中间序列设长度为 N我们要找到一个位置 k使得中间序列的前 k 个元素恰好等于初始序列前 k 个元素排序后的结果中间序列的第 k1 到第 N 个元素与初始序列的第 k1 到第 N 个元素完全一致。第一个条件保证“前缀是已排序区”第二个条件保证“后缀没被动过”。两个条件同时满足才能判定为插入排序的中间状态。这里有个容易忽略的点k 应该取多大理论上插入排序的中间状态对应的是“已经插入了 k 个元素”的状态k 可以从 1 到 N。但我们要找的是能匹配给定中间序列的那个 k。实操中我们可以从 k1 开始枚举找到第一个满足条件的 k然后对初始序列的前 k1 个元素排序输出结果就是“下一步迭代后的序列”。我实测下来枚举 k 的时候有个小优化先找到中间序列中“前缀有序”的最大长度然后在这个范围内枚举能省不少无效判断。不过对于这类题的数据规模N 通常不超过 100直接暴力枚举完全够用没必要过度优化。3.2 归并排序指纹的精确判断方法归并排序的中间序列判断起来稍微绕一点。核心是序列被切成若干个有序段每段长度是 2 的幂次。但“每段长度是 2 的幂次”这个描述不够精确因为最后一段可能不满而且段与段之间的边界要能对上。更精确的判断方法是从段长 len 1 开始模拟归并排序的合并过程。对于每个 len检查当前序列是否满足“每 len 个元素为一段段内有序”。如果满足说明当前处于“合并完长度为 len 的段”这个阶段。然后 len 翻倍继续检查。直到找到某个 len 使得条件满足且 len 翻倍后条件不再满足或者已经全序就说明当前中间序列对应的是这个阶段。等等这个描述还是有点模糊。让我换个更直接的说法归并排序的中间状态一定对应某个“段长” LL 1, 2, 4, 8, ...使得序列被分成 ceil(N/L) 段每段内部有序且除了最后一段每段长度都是 L。我们要找的就是这个 L然后对每个长度为 L 的段两两合并得到下一步的结果。判断的时候从 L1 开始试找到最大的满足条件的 L因为 L 越大分段越粗条件越容易满足但我们要的是“当前实际处于的阶段”。实际上正确的做法是找到最小的 L使得序列在“段长 L”的划分下每段有序且 L 翻倍后不再满足。这个 L 就是当前阶段。注意这里有个陷阱。如果序列本身已经完全有序那么对于任意 L条件都满足。这时候按题目约定应该优先判插入排序所以归并排序的判断逻辑要放在插入排序之后且要能正确处理“全序”这种边界。3.3 两种指纹的边界情况处理边界情况是这类题的重灾区我列几个必须处理的N1序列只有一个元素插入排序和归并排序的中间状态都是它本身。按约定判插入排序下一步还是它本身。初始序列已全序同上判插入排序下一步不变。中间序列等于初始序列说明还没开始排序或者排序第一步没改变序列。判插入排序下一步是对前两个元素排序。中间序列已全序但初始序列未全序可能是插入排序的最后一步也可能是归并排序的最后一步。按约定判插入排序下一步不变因为已经全序了插入排序再插也不变。这些边界情况我建议你在写代码前先用纸笔把每种情况的期望输出写出来然后再写代码验证。直接上手写代码很容易在边界上翻车。4. 实操过程从读入到输出的完整实现4.1 数据结构与输入处理这类题的输入格式通常是第一行一个整数 N第二行 N 个整数是初始序列第三行 N 个整数是中间序列。我们用两个vectorint存下来即可。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint origin(n), mid(n); for (int i 0; i n; i) cin origin[i]; for (int i 0; i n; i) cin mid[i]; // 后续判断逻辑 return 0; }读入部分没什么好说的但有个细节不要假设输入序列的元素互不相同。虽然很多题面没说清楚但实际测试数据里可能有重复元素。这意味着你不能用“元素值唯一”来做任何假设判断必须基于位置和排序结果而不是值本身。4.2 插入排序的判断与下一步计算先实现插入排序的判断。核心是找到那个 k然后对前 k1 个元素排序输出。bool isInsertion(vectorint origin, vectorint mid, int k) { int n origin.size(); for (int i 1; i n; i) { // 检查前 i 个元素origin 前 i 个排序后是否等于 mid 前 i 个 vectorint sortedPrefix(origin.begin(), origin.begin() i); sort(sortedPrefix.begin(), sortedPrefix.end()); bool prefixMatch true; for (int j 0; j i; j) { if (sortedPrefix[j] ! mid[j]) { prefixMatch false; break; } } if (!prefixMatch) continue; // 检查后缀origin 和 mid 从 i 开始是否完全一致 bool suffixMatch true; for (int j i; j n; j) { if (origin[j] ! mid[j]) { suffixMatch false; break; } } if (suffixMatch) { k i; return true; } } return false; }找到 k 之后下一步就是把 origin 的前 k1 个元素排序然后输出。void nextInsertion(vectorint origin, int k) { sort(origin.begin(), origin.begin() k 1); for (int i 0; i origin.size(); i) { if (i) cout ; cout origin[i]; } cout endl; }这里有个细节k 的含义是“已排序区长度为 k”所以下一步要排序的是前 k1 个元素。这个 1 很容易漏漏了就会输出错误结果。4.3 归并排序的判断与下一步计算归并排序的判断稍微复杂一点。我们从段长 L1 开始找到当前所处的阶段。bool isMerge(vectorint origin, vectorint mid, int L) { int n origin.size(); for (int len 1; len n; len * 2) { // 检查在段长 len 下mid 是否每段有序 bool allSorted true; for (int start 0; start n; start len) { int end min(start len, n); for (int j start 1; j end; j) { if (mid[j] mid[j-1]) { allSorted false; break; } } if (!allSorted) break; } if (!allSorted) continue; // 检查 len 翻倍后是否不再满足说明当前就是 len 阶段 int nextLen len * 2; bool nextSorted true; for (int start 0; start n; start nextLen) { int end min(start nextLen, n); for (int j start 1; j end; j) { if (mid[j] mid[j-1]) { nextSorted false; break; } } if (!nextSorted) break; } if (!nextSorted || nextLen n) { L len; return true; } } return false; }找到 L 之后下一步就是对每个长度为 L 的段两两合并。void nextMerge(vectorint origin, int L) { int n origin.size(); for (int start 0; start n; start 2 * L) { int mid min(start L, n); int end min(start 2 * L, n); // 合并 [start, mid) 和 [mid, end) vectorint merged; int i start, j mid; while (i mid j end) { if (origin[i] origin[j]) merged.push_back(origin[i]); else merged.push_back(origin[j]); } while (i mid) merged.push_back(origin[i]); while (j end) merged.push_back(origin[j]); for (int k 0; k merged.size(); k) { origin[start k] merged[k]; } } for (int i 0; i n; i) { if (i) cout ; cout origin[i]; } cout endl; }注意合并的时候用的是而不是这是为了保证稳定性。虽然这题不考稳定性但养成好习惯没坏处。4.4 主流程串联与输出格式把上面的逻辑串起来主流程就是先判插入排序命中就输出插入排序的下一步否则判归并排序输出归并排序的下一步。int main() { int n; cin n; vectorint origin(n), mid(n); for (int i 0; i n; i) cin origin[i]; for (int i 0; i n; i) cin mid[i]; int k; if (isInsertion(origin, mid, k)) { cout Insertion Sort endl; nextInsertion(origin, k); } else { int L; isMerge(origin, mid, L); cout Merge Sort endl; nextMerge(origin, L); } return 0; }输出格式要注意题目通常要求先输出排序类型Insertion Sort或Merge Sort再输出下一步的序列序列元素之间用空格分隔行末不能有多余空格。我上面用if (i) cout ;的方式处理能保证格式正确。5. 常见问题与排查技巧实录5.1 为什么我的插入排序判断总是漏掉某些情况最常见的原因是前缀匹配的判断写错了。很多人会写成“检查 mid 的前 k 个元素是否升序”这是不对的。正确的判断是“origin 的前 k 个元素排序后是否等于 mid 的前 k 个元素”。这两者的区别在于如果 origin 前 k 个元素本身不是升序那么 mid 前 k 个元素升序并不能说明它们来自 origin 的前 k 个元素。举个例子origin [3, 1, 2]mid [1, 2, 3]。mid 前 3 个元素升序但 origin 前 3 个元素排序后是 [1, 2, 3]确实等于 mid 前 3 个。但如果 mid [1, 3, 2]前 3 个不升序直接排除。再如果 origin [2, 3, 1]mid [2, 3, 1]mid 前 2 个升序origin 前 2 个排序后是 [2, 3]等于 mid 前 2 个后缀 [1] 也一致所以 k2 是有效的。提示判断前缀匹配时一定要用“排序后比对”不要用“是否升序”来偷懒。5.2 归并排序的段长 L 到底怎么确定这是另一个高频翻车点。很多人搞不清楚“当前处于哪个段长阶段”。我的经验是从 L1 开始找到第一个使得“段长 L 下每段有序”且“段长 2L 下不是每段有序”的 L。如果 L 一直翻倍到超过 N 都满足“每段有序”说明序列已经全序这时候按约定应该判插入排序所以归并排序的判断逻辑实际上不会走到这一步。还有一个细节当 N 不是 2 的幂次时最后一段可能不满 L。判断“每段有序”时最后一段也要检查但它的长度是 N mod L如果不为 0。这个边界很容易漏。5.3 常见问题速查表问题现象可能原因排查方法插入排序判断全部失败前缀匹配用了“升序”而非“排序后比对”打印 origin 前 k 个排序结果和 mid 前 k 个对比归并排序判断全部失败段长 L 的确定逻辑有误手动模拟 L1,2,4 的检查过程输出格式错误行末多了空格或少了空格用if (i) cout ;统一处理边界用例N1崩溃循环边界没处理好单独测试 N1 的情况两序重合时判错没有优先判插入排序确保插入排序判断在前重复元素导致判断错误用了值唯一性假设检查所有判断是否只依赖位置和排序结果5.4 我踩过的三个坑第一个坑是把插入排序的 k 理解成了“已排序区最后一个元素的下标”。实际上 k 是“已排序区的长度”所以下一步要排序的是前 k1 个元素。这个 off-by-one 让我在一个测试点上卡了很久后来打印中间变量才发现。第二个坑是归并排序判断时忘了检查“L 翻倍后不再满足”这个条件。结果对于已经全序的序列L1 就满足了“每段有序”直接误判为归并排序的 L1 阶段。加上翻倍检查后全序序列会一直翻倍到超过 N然后被插入排序截胡逻辑就对了。第三个坑是合并两个有序段时边界处理写错。特别是最后一段不满 2L 的情况end min(start 2*L, n)这个 min 不能漏否则会越界访问。这个坑在 N 不是 2 的幂次时必现。5.5 一个实用的调试技巧如果你实在判断不出来可以把两种排序的每一步都打印出来然后拿给定的中间序列去比对。这个方法虽然笨但极其有效尤其是当你对指纹判断还没建立直觉的时候。打印的时候注意把每一步的序列和对应的 k 或 L 都打出来这样你能清楚地看到“第几步之后得到了给定的中间序列”。我当年就是靠这个方法把一道类似的题从“完全没思路”磨到了“闭着眼睛都能写”。过程虽然慢但建立起来的直觉是抄答案抄不来的。6. 从这题延伸出去过程思维比结果思维更值钱这道题表面上是考排序实际上考的是你对算法执行过程的理解深度。平时我们写代码关注的是输入和输出中间过程是黑盒。但这道题逼着你把黑盒打开去看每一步到底发生了什么。这种“过程思维”在实际工作中非常值钱——当你调优一个慢查询、排查一个并发 bug、分析一个内存泄漏时你需要的正是这种“能想象出中间每一步状态”的能力。我在实际带人的时候发现能把这题讲清楚的人往往在排查线上问题时也更有一套。因为他们习惯了“不只看结果还要看过程”。反过来那些只会调库、从不关心底层实现的人遇到稍微偏一点的问题就容易抓瞎。这题还有一个隐藏价值它让你意识到同一个结果可能来自不同的过程。插入排序和归并排序在某些中间状态上会重合就像两条不同的路可能在某一点相交。判断“从哪条路来”需要看更早的轨迹而不是只看当前点。这个思路在日志分析、链路追踪、状态机调试里都是通用的。最后分享一个小技巧如果你想把这道题练透可以试着把两种排序的中间状态全部枚举出来画成一张状态转移图。你会发现插入排序的状态是一条链每步只前进一步而归并排序的状态是一棵树每层合并一批段。这张图能帮你把两种算法的本质差异看得清清楚楚。我当年画完这张图之后再遇到类似的“过程判断题”基本都能一眼看出答案。 
长河君 · 2026/10/21 13:29:51 · 阅读 1.2k 插入排序还是归并排序？从中间序列识别排序算法指纹
1. 从一道判题说起为什么“插入排序还是归并排序”值得单独拎出来讲“7-273 插入排序还是归并排序 (25 分)”这个标题第一次看到的人大概率会愣一下排序算法我熟插入排序、归并排序都是教科书级别的老面孔可“判断某段中间序列到底来自哪种排序”这件事为什么能单独成题还值 25 分我当年第一次刷到这类题时也犯嘀咕直到自己动手把两种排序的“中间过程”逐帧打印出来对比才意识到这题考的根本不是“会不会写排序”而是你对排序过程的理解到底停留在结果层还是深入到了过程层。先把题目场景说清楚。典型的题面是这样的给定一个长度为 N 的初始序列再给定一个“中间序列”也就是某一步排序后得到的序列要求你判断这个中间序列是由插入排序产生的还是由归并排序产生的并输出下一步迭代后的结果。如果两种排序在某一步恰好得到相同的序列题目通常约定优先判定为插入排序。这个约定不是随便定的后面会详细讲为什么。这道题能解决什么问题它逼着你去回答一个非常本质的问题同样是“部分有序”的中间状态插入排序和归并排序留下的“指纹”是不一样的。插入排序的特点是“前缀有序、后缀原封不动”归并排序的特点是“若干个长度递增的有序段拼接”。抓住这两个指纹判断就变成了模式识别而不是真的去模拟两遍排序再比对——当然模拟两遍也能过但那是另一种思路各有取舍。适合谁来参考我觉得有三类人特别值得花时间啃透这题。第一类是正在准备算法类上机考试的同学这类“过程判断题”是高频考点考的是对算法执行轨迹的敏感度。第二类是已经工作、但想回头补一补算法基本功的开发者平时写业务代码调个sort()就完事了真让你说清楚底层每一步发生了什么未必讲得利索。第三类是带课或做辅导的人这题是个极好的教学素材能把“算法过程可视化”这件事讲得非常具体。我下面会从整体思路、两种排序的指纹特征、完整实操流程、常见坑与排查四个大块展开中间穿插我踩过的坑和实测有效的技巧。代码用 C 写因为这类题的输入输出格式和 STL 容器配合起来最顺手但思路是语言无关的你用 Python 或 Java 照样能套。2. 整体思路拆解为什么“识别指纹”比“模拟排序”更聪明2.1 两种排序的中间状态到底差在哪要判断一个中间序列来自哪种排序最直接的办法当然是拿初始序列分别跑一遍插入排序和归并排序每一步都记录快照然后拿给定的中间序列去比对谁先匹配上就是谁。这个思路绝对正确也绝对能过但它的代价是你要完整实现两套排序并且维护所有中间状态代码量大、容易写错而且一旦题目数据规模上去模拟的开销也不小。更聪明的做法是直接识别中间序列的结构特征也就是我前面说的“指纹”。我们分别来看。插入排序的执行逻辑是把序列分成“已排序区”和“未排序区”初始时已排序区只有第一个元素然后每次从未排序区取第一个元素插入到已排序区的正确位置。关键点来了——在任意一步中间状态已排序区永远是原序列的一个前缀而且这个前缀是升序的未排序区则完全保持原样一个元素都没动过。这就是插入排序最鲜明的指纹前缀有序后缀原封不动。归并排序这里指自底向上的迭代版本也是这类题默认的版本的执行逻辑是先两两合并长度为 1 的段得到若干长度 2 的有序段再两两合并长度 2 的段得到若干长度 4 的有序段以此类推直到整个序列有序。所以它的中间状态指纹是序列被切成若干个有序段每段的长度是 2 的幂次最后一段可能不满而且这些段是连续拼接的。把这两个指纹摆在一起判断逻辑就非常清晰了。给定中间序列先检查它是不是“前缀有序、后缀原样”——如果是那它极可能来自插入排序如果不是再检查它是不是“若干个 2 的幂次长度有序段拼接”——如果是那就是归并排序。提示这里的“前缀有序”判断有个细节不是要求整个前缀严格递增而是要求前缀部分恰好是初始序列前若干元素排序后的结果。换句话说你要验证的是“初始序列的前 k 个元素排序后是否等于中间序列的前 k 个元素”而不是简单看中间序列前 k 个是不是升序。这个区别是很多人第一次做这题时栽跟头的地方。2.2 为什么题目约定“相同时优先判插入排序”这个约定乍看像是出题人偷懒其实有它的道理。考虑一个极端情况初始序列本身就已经有序了。这时候插入排序的“第一步”之后序列不变归并排序的“第一步”之后序列也不变两者完全重合。如果不做约定判题就没法给出唯一答案。那为什么优先判插入排序而不是归并排序我的理解是从“最小改动”的角度看插入排序在已有序序列上的表现更“自然”——它本来就不需要做任何实质性的移动。而且从实现角度插入排序的指纹检查前缀有序比归并排序的指纹检查2 的幂次分段更简单先检查简单的、命中率高的符合工程上的“短路原则”。这个约定你在写代码时必须严格遵守否则测试点里那些“两序重合”的用例会直接把你卡死。2.3 两种思路的取舍模拟 vs 指纹我把两种思路的对比整理成表格方便你根据场景选择。对比维度模拟排序法指纹识别法核心逻辑跑两遍排序逐步比对快照直接检查中间序列的结构特征代码量大需实现两套排序快照管理小主要是特征判断逻辑时间复杂度O(N² log N) 级别含快照比对O(N log N) 或 O(N²)取决于实现出错概率高快照边界容易搞错中指纹判断的边界要小心适用场景想彻底理解排序过程时应试、追求代码简洁时可扩展性差换一种排序就要重写好加新排序只需加新指纹我个人的建议是第一次做这题时用模拟法把两种排序的每一步都打印出来看建立直觉之后再用指纹法重写一遍体会两种思路的差异。这个学习路径比直接抄指纹法答案有价值得多。3. 核心细节解析指纹判断的每一步都要抠清楚3.1 插入排序指纹的精确判断方法插入排序的中间序列设长度为 N我们要找到一个位置 k使得中间序列的前 k 个元素恰好等于初始序列前 k 个元素排序后的结果中间序列的第 k1 到第 N 个元素与初始序列的第 k1 到第 N 个元素完全一致。第一个条件保证“前缀是已排序区”第二个条件保证“后缀没被动过”。两个条件同时满足才能判定为插入排序的中间状态。这里有个容易忽略的点k 应该取多大理论上插入排序的中间状态对应的是“已经插入了 k 个元素”的状态k 可以从 1 到 N。但我们要找的是能匹配给定中间序列的那个 k。实操中我们可以从 k1 开始枚举找到第一个满足条件的 k然后对初始序列的前 k1 个元素排序输出结果就是“下一步迭代后的序列”。我实测下来枚举 k 的时候有个小优化先找到中间序列中“前缀有序”的最大长度然后在这个范围内枚举能省不少无效判断。不过对于这类题的数据规模N 通常不超过 100直接暴力枚举完全够用没必要过度优化。3.2 归并排序指纹的精确判断方法归并排序的中间序列判断起来稍微绕一点。核心是序列被切成若干个有序段每段长度是 2 的幂次。但“每段长度是 2 的幂次”这个描述不够精确因为最后一段可能不满而且段与段之间的边界要能对上。更精确的判断方法是从段长 len 1 开始模拟归并排序的合并过程。对于每个 len检查当前序列是否满足“每 len 个元素为一段段内有序”。如果满足说明当前处于“合并完长度为 len 的段”这个阶段。然后 len 翻倍继续检查。直到找到某个 len 使得条件满足且 len 翻倍后条件不再满足或者已经全序就说明当前中间序列对应的是这个阶段。等等这个描述还是有点模糊。让我换个更直接的说法归并排序的中间状态一定对应某个“段长” LL 1, 2, 4, 8, ...使得序列被分成 ceil(N/L) 段每段内部有序且除了最后一段每段长度都是 L。我们要找的就是这个 L然后对每个长度为 L 的段两两合并得到下一步的结果。判断的时候从 L1 开始试找到最大的满足条件的 L因为 L 越大分段越粗条件越容易满足但我们要的是“当前实际处于的阶段”。实际上正确的做法是找到最小的 L使得序列在“段长 L”的划分下每段有序且 L 翻倍后不再满足。这个 L 就是当前阶段。注意这里有个陷阱。如果序列本身已经完全有序那么对于任意 L条件都满足。这时候按题目约定应该优先判插入排序所以归并排序的判断逻辑要放在插入排序之后且要能正确处理“全序”这种边界。3.3 两种指纹的边界情况处理边界情况是这类题的重灾区我列几个必须处理的N1序列只有一个元素插入排序和归并排序的中间状态都是它本身。按约定判插入排序下一步还是它本身。初始序列已全序同上判插入排序下一步不变。中间序列等于初始序列说明还没开始排序或者排序第一步没改变序列。判插入排序下一步是对前两个元素排序。中间序列已全序但初始序列未全序可能是插入排序的最后一步也可能是归并排序的最后一步。按约定判插入排序下一步不变因为已经全序了插入排序再插也不变。这些边界情况我建议你在写代码前先用纸笔把每种情况的期望输出写出来然后再写代码验证。直接上手写代码很容易在边界上翻车。4. 实操过程从读入到输出的完整实现4.1 数据结构与输入处理这类题的输入格式通常是第一行一个整数 N第二行 N 个整数是初始序列第三行 N 个整数是中间序列。我们用两个vectorint存下来即可。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint origin(n), mid(n); for (int i 0; i n; i) cin origin[i]; for (int i 0; i n; i) cin mid[i]; // 后续判断逻辑 return 0; }读入部分没什么好说的但有个细节不要假设输入序列的元素互不相同。虽然很多题面没说清楚但实际测试数据里可能有重复元素。这意味着你不能用“元素值唯一”来做任何假设判断必须基于位置和排序结果而不是值本身。4.2 插入排序的判断与下一步计算先实现插入排序的判断。核心是找到那个 k然后对前 k1 个元素排序输出。bool isInsertion(vectorint origin, vectorint mid, int k) { int n origin.size(); for (int i 1; i n; i) { // 检查前 i 个元素origin 前 i 个排序后是否等于 mid 前 i 个 vectorint sortedPrefix(origin.begin(), origin.begin() i); sort(sortedPrefix.begin(), sortedPrefix.end()); bool prefixMatch true; for (int j 0; j i; j) { if (sortedPrefix[j] ! mid[j]) { prefixMatch false; break; } } if (!prefixMatch) continue; // 检查后缀origin 和 mid 从 i 开始是否完全一致 bool suffixMatch true; for (int j i; j n; j) { if (origin[j] ! mid[j]) { suffixMatch false; break; } } if (suffixMatch) { k i; return true; } } return false; }找到 k 之后下一步就是把 origin 的前 k1 个元素排序然后输出。void nextInsertion(vectorint origin, int k) { sort(origin.begin(), origin.begin() k 1); for (int i 0; i origin.size(); i) { if (i) cout ; cout origin[i]; } cout endl; }这里有个细节k 的含义是“已排序区长度为 k”所以下一步要排序的是前 k1 个元素。这个 1 很容易漏漏了就会输出错误结果。4.3 归并排序的判断与下一步计算归并排序的判断稍微复杂一点。我们从段长 L1 开始找到当前所处的阶段。bool isMerge(vectorint origin, vectorint mid, int L) { int n origin.size(); for (int len 1; len n; len * 2) { // 检查在段长 len 下mid 是否每段有序 bool allSorted true; for (int start 0; start n; start len) { int end min(start len, n); for (int j start 1; j end; j) { if (mid[j] mid[j-1]) { allSorted false; break; } } if (!allSorted) break; } if (!allSorted) continue; // 检查 len 翻倍后是否不再满足说明当前就是 len 阶段 int nextLen len * 2; bool nextSorted true; for (int start 0; start n; start nextLen) { int end min(start nextLen, n); for (int j start 1; j end; j) { if (mid[j] mid[j-1]) { nextSorted false; break; } } if (!nextSorted) break; } if (!nextSorted || nextLen n) { L len; return true; } } return false; }找到 L 之后下一步就是对每个长度为 L 的段两两合并。void nextMerge(vectorint origin, int L) { int n origin.size(); for (int start 0; start n; start 2 * L) { int mid min(start L, n); int end min(start 2 * L, n); // 合并 [start, mid) 和 [mid, end) vectorint merged; int i start, j mid; while (i mid j end) { if (origin[i] origin[j]) merged.push_back(origin[i]); else merged.push_back(origin[j]); } while (i mid) merged.push_back(origin[i]); while (j end) merged.push_back(origin[j]); for (int k 0; k merged.size(); k) { origin[start k] merged[k]; } } for (int i 0; i n; i) { if (i) cout ; cout origin[i]; } cout endl; }注意合并的时候用的是而不是这是为了保证稳定性。虽然这题不考稳定性但养成好习惯没坏处。4.4 主流程串联与输出格式把上面的逻辑串起来主流程就是先判插入排序命中就输出插入排序的下一步否则判归并排序输出归并排序的下一步。int main() { int n; cin n; vectorint origin(n), mid(n); for (int i 0; i n; i) cin origin[i]; for (int i 0; i n; i) cin mid[i]; int k; if (isInsertion(origin, mid, k)) { cout Insertion Sort endl; nextInsertion(origin, k); } else { int L; isMerge(origin, mid, L); cout Merge Sort endl; nextMerge(origin, L); } return 0; }输出格式要注意题目通常要求先输出排序类型Insertion Sort或Merge Sort再输出下一步的序列序列元素之间用空格分隔行末不能有多余空格。我上面用if (i) cout ;的方式处理能保证格式正确。5. 常见问题与排查技巧实录5.1 为什么我的插入排序判断总是漏掉某些情况最常见的原因是前缀匹配的判断写错了。很多人会写成“检查 mid 的前 k 个元素是否升序”这是不对的。正确的判断是“origin 的前 k 个元素排序后是否等于 mid 的前 k 个元素”。这两者的区别在于如果 origin 前 k 个元素本身不是升序那么 mid 前 k 个元素升序并不能说明它们来自 origin 的前 k 个元素。举个例子origin [3, 1, 2]mid [1, 2, 3]。mid 前 3 个元素升序但 origin 前 3 个元素排序后是 [1, 2, 3]确实等于 mid 前 3 个。但如果 mid [1, 3, 2]前 3 个不升序直接排除。再如果 origin [2, 3, 1]mid [2, 3, 1]mid 前 2 个升序origin 前 2 个排序后是 [2, 3]等于 mid 前 2 个后缀 [1] 也一致所以 k2 是有效的。提示判断前缀匹配时一定要用“排序后比对”不要用“是否升序”来偷懒。5.2 归并排序的段长 L 到底怎么确定这是另一个高频翻车点。很多人搞不清楚“当前处于哪个段长阶段”。我的经验是从 L1 开始找到第一个使得“段长 L 下每段有序”且“段长 2L 下不是每段有序”的 L。如果 L 一直翻倍到超过 N 都满足“每段有序”说明序列已经全序这时候按约定应该判插入排序所以归并排序的判断逻辑实际上不会走到这一步。还有一个细节当 N 不是 2 的幂次时最后一段可能不满 L。判断“每段有序”时最后一段也要检查但它的长度是 N mod L如果不为 0。这个边界很容易漏。5.3 常见问题速查表问题现象可能原因排查方法插入排序判断全部失败前缀匹配用了“升序”而非“排序后比对”打印 origin 前 k 个排序结果和 mid 前 k 个对比归并排序判断全部失败段长 L 的确定逻辑有误手动模拟 L1,2,4 的检查过程输出格式错误行末多了空格或少了空格用if (i) cout ;统一处理边界用例N1崩溃循环边界没处理好单独测试 N1 的情况两序重合时判错没有优先判插入排序确保插入排序判断在前重复元素导致判断错误用了值唯一性假设检查所有判断是否只依赖位置和排序结果5.4 我踩过的三个坑第一个坑是把插入排序的 k 理解成了“已排序区最后一个元素的下标”。实际上 k 是“已排序区的长度”所以下一步要排序的是前 k1 个元素。这个 off-by-one 让我在一个测试点上卡了很久后来打印中间变量才发现。第二个坑是归并排序判断时忘了检查“L 翻倍后不再满足”这个条件。结果对于已经全序的序列L1 就满足了“每段有序”直接误判为归并排序的 L1 阶段。加上翻倍检查后全序序列会一直翻倍到超过 N然后被插入排序截胡逻辑就对了。第三个坑是合并两个有序段时边界处理写错。特别是最后一段不满 2L 的情况end min(start 2*L, n)这个 min 不能漏否则会越界访问。这个坑在 N 不是 2 的幂次时必现。5.5 一个实用的调试技巧如果你实在判断不出来可以把两种排序的每一步都打印出来然后拿给定的中间序列去比对。这个方法虽然笨但极其有效尤其是当你对指纹判断还没建立直觉的时候。打印的时候注意把每一步的序列和对应的 k 或 L 都打出来这样你能清楚地看到“第几步之后得到了给定的中间序列”。我当年就是靠这个方法把一道类似的题从“完全没思路”磨到了“闭着眼睛都能写”。过程虽然慢但建立起来的直觉是抄答案抄不来的。6. 从这题延伸出去过程思维比结果思维更值钱这道题表面上是考排序实际上考的是你对算法执行过程的理解深度。平时我们写代码关注的是输入和输出中间过程是黑盒。但这道题逼着你把黑盒打开去看每一步到底发生了什么。这种“过程思维”在实际工作中非常值钱——当你调优一个慢查询、排查一个并发 bug、分析一个内存泄漏时你需要的正是这种“能想象出中间每一步状态”的能力。我在实际带人的时候发现能把这题讲清楚的人往往在排查线上问题时也更有一套。因为他们习惯了“不只看结果还要看过程”。反过来那些只会调库、从不关心底层实现的人遇到稍微偏一点的问题就容易抓瞎。这题还有一个隐藏价值它让你意识到同一个结果可能来自不同的过程。插入排序和归并排序在某些中间状态上会重合就像两条不同的路可能在某一点相交。判断“从哪条路来”需要看更早的轨迹而不是只看当前点。这个思路在日志分析、链路追踪、状态机调试里都是通用的。最后分享一个小技巧如果你想把这道题练透可以试着把两种排序的中间状态全部枚举出来画成一张状态转移图。你会发现插入排序的状态是一条链每步只前进一步而归并排序的状态是一棵树每层合并一批段。这张图能帮你把两种算法的本质差异看得清清楚楚。我当年画完这张图之后再遇到类似的“过程判断题”基本都能一眼看出答案。