排序中间状态识别

2026 大纲 七（十二）排序算法的分析与应用 · 中间状态反推部分（横向对比与选型见《排序算法对比》）。

一条单向的因果链，倒着走

这类题的形式很固定：给一个序列在排序过程中的某个快照，问"这是哪种排序的第几趟"，或者"下列哪个不可能是某种排序的第 $k$ 趟结果"。

它们全都建立在同一条因果链上：

算法怎样扩大有序区 $\Rightarrow$ 一趟后必然成立的不变量 $\Rightarrow$ 数组呈现的结构特征

这条链是单向的：算法定了，特征就定了。所以"从中间状态反推算法"就是逆着它往回走——看到什么特征，就去问"哪种扩大有序区的方式会留下这个特征"。

不需要背中间状态清单，只需要记住每种算法"一趟到底干了什么"。

先动手看一眼

加载可视化中...

八种算法的不变量与特征

排序算法	不变量（第 $k$ 趟结束后必然成立）	数组呈现的结构特征
直接／折半插入	原序列的前 $k+1$ 个元素已排好序，其余元素从未被触碰	前 $k+1$ 个局部有序（不一定是全局最小的几个），后部与初始序列逐位相同
希尔	序列是 $d$-有序的：任意 $i$ 有 $A[i]\le A[i+d]$	间隔 $d$ 的各子序列分别有序；整体"基本有序"但前缀通常仍乱
冒泡	一端的 $k$ 个元素是全局最大（最小）的 $k$ 个，已有序且就位；其余部分只经历过相邻交换	一端聚集 $k$ 个全局最值且有序、就位
快速	每趟划分使枢轴到达最终位置（左边全 $\le$ 它、右边全 $\ge$ 它）	存在分界元素；第 1 趟后至少 1 个，前 $k$ 趟累计至多 $2^k-1$ 个
简单选择	前 $k$ 个位置是全局最小的 $k$ 个元素，已有序且就位	头部聚集 $k$ 个全局最值且有序、就位
堆	尾部 $k$ 个是全局最大的 $k$ 个且有序（大根堆），前部满足堆序	尾部就位 + 前部是合法大根堆
二路归并	序列被切成若干连续段，每段内部有序，段长 $2^k$（最后一段可不足）	连续等长段各自有序
基数（LSD）	按已处理的低 $k$ 位整体有序	取每个元素的末 $k$ 位看是单调不减的；完整关键字的大小关系可能仍乱

这张表里最值得单独拎出来的是四条：

🔴 每趟必有元素就位的只有四个：冒泡、简单选择、快排、堆排。 因为这一趟看过全局（相邻比较有传递性、显式扫一遍未排序区、划分时两端扫描）。插入、希尔、归并、基数都不保证——它们每趟只看过局部（前 $i$ 个／段内／一位）。

🔴 插入类最硬的指纹是"后缀与初始序列逐位相同"，而不是"前缀有序"。前缀有序是好几种算法共有的，后缀没被碰过却只有插入类才有。

🔴 快排就位的不是极值，是枢轴，通常在区间中间。分界元素的个数只能用来排除、不能用来断定趟数。

🔴 直接插入与折半插入的中间状态完全相同、无法区分——两者的不变量本来就一样，只在"找插入位置的方式"上不同。看到这两个同时出现在选项里，说明题目考的一定是别的点。

⚠️ 还有一个措辞坑：希尔的"一趟"指一个增量（把全部 $d$ 组都排完），不是一个组。

三组最接近的算法，各自怎么区分

① 插入 vs 简单选择——前缀都"有序"。

判别只看一件事：前缀里的元素是不是全局最小的那几个。简单选择 2 趟后 $(1,2,\dots )$——1、2 正是全序列最小的两个 $\Rightarrow$ 选择；直接插入 2 趟后 $(3,7,8,\dots )$——3、7、8 不是最小的三个 $\Rightarrow$ 插入。

另一条更硬的依据：插入排序的后缀与初始序列逐位相同（还没碰过），而选择排序因为发生过交换，后缀通常已经变样。

机械做法：把前缀里的最大值与后缀里的最小值比一下——前者不大于后者就是"已就位"（选择类），否则只是"局部有序"（插入类）。

② 冒泡 vs 堆排——尾部都是"最大的 $k$ 个有序"。

判别只能看前部是否满足堆序：按完全二叉树逐个检查 $A[i]\ge A[2i+1]$ 且 $A[i]\ge A[2i+2]$（0 起下标）。

堆排 2 趟后前部 $(6,4,5,2,1,3)$：$6\ge 4,5$；$4\ge 2,1$；$5\ge 3$ —— 是大根堆；冒泡 2 趟后前部 $(3,4,1,5,2,6)$：第一步 $3<4$ 就破坏了堆序 —— 不是堆。

一条更快的粗筛：堆排的前部首元素必是前部的最大值（它就是当前堆顶）；冒泡的前部首元素通常不是——冒泡每趟都把大元素往后赶。

③ 归并 vs 希尔——整体都"半有序"。

两者的中间状态都是"半有序"，但有序的方向完全不同：归并的有序是连续的（按段长 2、4、8 直接切开，段内有序）；希尔的有序是跳跃的（按 $d=n/2,n/4,\dots$ 抽取间隔 $d$ 的子序列，各子序列内部有序，而连续切开则通常无序）。

归并的连续段边界处通常有一个明显的"跌落"（如 $8\to 1$），而希尔的连续切分一般对不齐。

判"不可能是快排第 $k$ 趟结果"

这是快排在这类题里的固定问法，判断标准是：

🔴 第 $k$ 趟结束时，至少有 $k$ 个元素已就位；一个元素就位的标志是"它左边的全部 $\le$ 它，右边的全部 $\ge$ 它"。

手法：从左往右扫一遍记录前缀最大值，从右往左扫一遍记录后缀最小值；某个位置若"前缀最大值 $=$ 自己"且"后缀最小值 $=$ 自己"，它就已就位。数一数够不够 $k$ 个。

以 2, 3, 5, 4, 6, 7, 9 为例（问是否可能是第 2 趟结果）：

下标	0	1	2	3	4	5	6
值	2	3	5	4	6	7	9
前缀最大	2	3	5	5	6	7	9
后缀最小	2	3	4	4	6	7	9
就位？	✓	✓	✗	✗	✓	✓	✓

5 个就位 $\ge 2$，可能。四个选项里数不够 $k$ 个的那个才是答案。

⚠️ 两处要说准：① 一个状态里满足分界性质的元素可以多于真正的枢轴数（碰巧分界的元素不矛盾），所以这个计数只能用来排除"分界元素太少"的情形；② 前 $k$ 趟累计归位的枢轴数 $\le 2^k-1$，所以第 2 趟结束时至少 2 个、最多 3 个。

反过来用：不变量被违反 = 一定不是这种排序

不变量是必要条件：算法跑完第 $k$ 趟，状态必然满足它。所以反过来，只要发现某个状态违反了某算法的不变量，就能确定地排除它——这个方向的推理是严密的，比"符合特征所以是它"更可靠（后者只能说"可能是"）。

观察到	一定不是	理由
后缀与初始序列不一致	直接／折半插入的第 $k$ 趟（$k$ 小于该位置）	插入类根本没碰过后缀
前缀有序但不是全局最小的那几个	简单选择排序	它的前缀必然是全局最小的 $k$ 个
尾部就位但前部不满足堆序	堆排序	前部必须始终是合法大根堆
尾部就位的元素不是全局最大的那几个	冒泡、堆排序	两者就位的都必须是全局最值
找不到任何左边全 $\le$ 它、右边全 $\ge$ 它的元素	快速排序（任何趟）	至少有一个枢轴必须已归位
连续段切不齐、间隔子序列也不有序	归并、希尔	两者的有序性一个是连续的、一个是跳跃的
取末 $k$ 位（$k=1,2,\dots$）都不是单调不减	基数排序（任何趟）	第 $k$ 趟后必然按低 $k$ 位有序

⚠️ 一条不能用的"判断方法"：不要拿"元素位置挪动得大不大"去排除基数排序。分配-收集只保证"按低 $k$ 位有序"，并不保证元素位置一定发生变动。反例：$(10,20,30,11)$ 按个位做完第 1 趟分配-收集，序列一个位置都没变（个位依次是 $0,0,0,1$，本来就有序），但它显然还没排好。只有从不变量导出的条件才能用来排除。

同一序列跑七种排序的对照状态（想逐条核对不变量就展开）

初始序列统一为 (3, 8, 7, 4, 1, 5, 2, 6)，下表每个状态都按对应算法逐趟推出：

算法（第几趟后）	状态	不变量在这个状态上的体现
直接插入 · 2 趟	(3, 7, 8, 4, 1, 5, 2, 6)	前 3 个有序，但 1、2 还在后面——前缀有序 $\ne$ 全局最小；后 5 个与初始序列逐位相同
希尔 $d=4$ · 1 趟	(1, 5, 2, 4, 3, 8, 7, 6)	间隔 4 看：$\{1,3\}$、$\{5,8\}$、$\{2,7\}$、$\{4,6\}$ 各自有序；连续切开则无序
冒泡 · 2 趟	(3, 4, 1, 5, 2, 6, 7, 8)	尾部 7、8 是全局最大的两个，有序且就位；前部只经历过相邻交换
快排 · 1 趟（枢轴 3）	(2, 1, 3, 4, 7, 5, 8, 6)	3 的左边 $\{2,1\}$ 全 $\le 3$、右边全 $\ge 3$——枢轴到位，且它不是极值
简单选择 · 2 趟	(1, 2, 7, 4, 3, 5, 8, 6)	头部 1、2 是全局最小的两个，有序且就位
堆排 · 建初堆 + 2 趟	(6, 4, 5, 2, 1, 3, 7, 8)	尾部 7、8 就位；前部 $(6,4,5,2,1,3)$ 是合法大根堆
二路归并 · 2 趟	(3, 4, 7, 8, 1, 2, 5, 6)	段长 4 的两个连续段 $\{3,4,7,8\}$ 与 $\{1,2,5,6\}$ 各自有序

留意冒泡 2 趟与堆排 2 趟的尾部完全相同（都是 7、8 就位）——只看尾部分不出来，必须看前部。

用排除法走一遍：状态 $(3,4,1,5,2,6,7,8)$。

• 后缀被动过 $\Rightarrow$ 排除插入类；
• 头部 $(3,4)$ 不是全局最小的两个（1、2 还在后面）$\Rightarrow$ 排除简单选择；
• 尾部 $(7,8)$ 是全局最大的两个且有序 $\Rightarrow$ 剩下冒泡或堆排；
• 前部 $(3,4,1,5,2,6)$ 检查堆序：$3<4$，第一步就违反 $\Rightarrow$ 排除堆排；
• 只剩冒泡排序，且是第 2 趟。

"每趟至少一个元素就位"为什么恰好是那四个？ 因为"就位"意味着这个元素与其余所有元素的相对位置已经全部确定：交换类与选择类每趟都做了一次"与整个未排序区的比较"，所以能得出结论；插入类每趟只看了前 $i$ 个元素；归并每趟只在段内比较，跨段关系要等更高层归并；基数每趟只看一位。一句话概括：每趟是否"看过全局"，决定了每趟是否能有元素就位。

五类不变量的展开说明（想弄清每条特征怎么从算法推出来就展开）

插入类：为什么"前缀有序"却不能说"前缀就位"。 插入排序把第 $i+1$ 个元素插进前 $i$ 个已排好的元素里，它只看过前 $i+1$ 个元素：前缀内部一定有序，但前缀里的元素未必是整个序列最小的那几个——后面完全可能藏着更小的值，等轮到它时会插进来把前缀撑开。

选择类与交换类：一端聚集全局最值。 简单选择每趟从未排序区选出全局最小接到有序区末尾，冒泡每趟把全局最大交换到未排序区末尾——两者都保证"就位的一定是全局最值"。

快速排序：分界元素，不是极值。 枢轴通常不在区间端点，也通常不是极值，所以指纹是：

存在某个位置 $p$，使得 $A[0..p-1]$ 全部 $\le A[p]$、$A[p+1..n-1]$ 全部 $\ge A[p]$。

归并与希尔：连续段 vs 跳跃子序列。 归并的有序是连续的；希尔的有序是跳跃的。

基数排序：完整关键字可能仍然很乱。 LSD 每趟只按一位排序，中间状态里最大的数完全可能排在最前面（个位为 0 的话），这是它区别于所有比较类排序的特征。

考点速记

三条结论：

1. 中间状态不是要背的清单，是不变量的可见形式——记住每种算法"一趟干了什么"，状态自然推得出来。
2. 共有特征要靠"下一层"细分：尾部就位是冒泡与堆排共有的，靠前部堆序细分；前缀有序是插入与选择共有的，靠"是不是全局最小"和"后缀有没有被碰过"细分。
3. 排除与确认是不对称的：违反不变量 $\Rightarrow$ 一定不是（可靠）；符合特征 $\Rightarrow$ 只能说可能是。

这一节在真题里被考过的形式（下方「真题练习」与《排序算法对比》共用同一批题）：

• 给第 $k$ 趟结果，问"只能是"哪种排序：先用"后缀有没有被碰过"筛掉插入类，再用"就位的是不是全局最值"分开选择与插入，最后用堆序分开冒泡与堆排。
• 给前几趟结果，问"可能是"哪种排序：判断标准同上，但要注意"可能"意味着只需存在一种合法解释。
• 判某序列不可能是快排第 2 趟结果：扫前缀最大值 + 后缀最小值，数就位元素够不够 2 个。
• 由希尔某趟结果反推增量：按 $modd$ 分组验证每组是否升序（详见希尔排序）。
• 由序列变化表判断算法：给"初始 / 第 1 趟 / 第 2 趟"三行，逐个候选算法套不变量。
• 建大根堆的序列变化过程选择题：看的是建堆次序（从 $\lfloor n/2\rfloor$ 倒着来、一次下沉到底），详见堆排序。
• "每趟至少能确定一个元素最终位置"的有哪些：简单选择、快速、堆排三个（详见排序算法对比）。

易错：只看尾部分不出冒泡和堆排。 两者的尾部一模一样，必须检查前部堆序。

易错：插入类的指纹是"后缀没被碰过"，不是"前缀有序"。 后者是插入与选择共有的。

易错：别用"元素位置有没有变动"排除基数排序。 存在一趟分配收集后位置完全不变的合法情形。

教材出处

• "使有序区中记录的数目增加一个或几个的操作称为一趟排序"，以及插入类／交换类／选择类／归并类／分配类各自"如何扩大有序序列长度"的定义：严蔚敏《数据结构（C 语言版）》（第 2 版），p235
• 各算法逐趟中间状态的教材原例：直接插入排序过程（图 8.1，p237）、起泡排序过程（图 8.3，p242）、快速排序一趟划分与全过程（图 8.4，p244）、简单选择排序过程（图 8.6，p247）、堆排序过程（图 8.12，p253）、二路归并排序过程（图 8.13，p254）、希尔排序过程（图 8.2，p240）、链式基数排序的三趟分配与收集（图 8.15，p257–p258）
• 各算法不变量的推导见各自单篇的「教材出处」一节

相关知识

排序的基本概念（本篇全部不变量的源头）｜ 排序算法对比（本条目的另一半）｜ 直接插入排序｜希尔排序｜冒泡排序｜快速排序｜简单选择排序｜堆排序｜二路归并排序｜基数排序

相关文章

• 排序基本概念
• 直接插入排序
• 折半插入排序
• 希尔排序
• 冒泡排序
• 快速排序
• 简单选择排序
• 堆排序
• 归并排序
• 基数排序
• 计数排序
• 外部排序
• 排序算法对比与性能实测

交互体验

前往完整可视化页面 →

真题练习

相关真题（5题）

2023Q102分2022Q112分2021Q428分2019Q72分2012Q102分