Appearance
排序中间状态识别
为什么值得单独一篇
"给定初始序列和某个中间状态，问它是哪种排序第 k 趟的结果（或不可能是哪种排序）"——这是排序章选择题的第一高频题型，几乎年年出现。它考的不是会不会写排序，而是对每种算法"一趟干了什么"的指纹级理解。
本篇把散落在各算法文章里的判别线索收拢成一张表、一套流程，再用同一个序列做对照实验。
八种排序的"指纹"总表
| 排序算法 | 第 k 趟结束后的状态特征 |
|---|---|
| 直接/折半插入 | 前 k+1 个元素局部有序（是原序列前 k+1 个元素排好序的样子，不一定是全局最小），后部与初始序列完全一致 |
| 希尔 | 按当前增量 d 分组，间隔 d 的各子序列分别有序；整体"基本有序"但前缀通常无序 |
| 冒泡 | 一端聚集了 k 个全局最值且已有序、已就位；剩余部分只发生过相邻交换 |
| 快排 | 每趟划分使枢轴到达最终位置（左边全 ≤ 它、右边全 ≥ 它）；第 1 趟后至少 1 个、第 2 趟后至少 2 个（通常 3 个）元素满足该性质 |
| 简单选择 | 前 k 个位置是全局最小的 k 个元素且有序 |
| 堆排 | 尾部是全局最大的 k 个且有序（大根堆），前部满足堆序（每个结点 ≥ 其孩子） |
| 归并 | 等长段内部各自有序，段长 = 2ᵏ（最后一段可以不足） |
| 基数（LSD） | 按已处理的低 k 位整体有序，关键字大小关系可能仍乱 |
对照实验：同一序列跑七种排序
初始序列统一为 (3, 8, 7, 4, 1, 5, 2, 6)，下表每个状态都按算法逐步推出（建议自己先盖住右边推一遍）：
| 算法（第几趟后） | 状态 | 指纹在哪 |
|---|---|---|
| 直接插入 · 2 趟 | (3, 7, 8, 4, 1, 5, 2, 6) | 前 3 个有序，但 1、2 还在后面——前缀有序 ≠ 全局最小；后 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} 全 ≤ 3，右边全 ≥ 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 就位）——只看尾部分不出来，区分点在前部（见下面"三组易混"）。
判别流程：拿到题先看哪里
排除型题目（"不可能是哪种排序的第 2 趟"）反着用：逐个选项验证指纹，指纹对不上的就是答案。
三组最容易混的对比
① 插入 vs 简单选择——前缀都"有序"
判别只看一件事：前缀里的元素是不是全局最小的那几个。
- 简单选择 2 趟后 (1, 2, …)——1、2 正是全序列最小的两个 → 选择
- 直接插入 2 趟后 (3, 7, 8, …)——3、7、8 不是最小的三个（1、2 还在后面）→ 插入
另一个佐证：插入排序的后部与初始序列逐位相同（还没碰过），选择排序的后部因为换位通常变了样。
② 冒泡 vs 堆排——尾部都是"最大的 k 个有序"
看前部：堆排的前部必须满足堆序（按完全二叉树检查每个 a[i] ≥ a[2i+1]、a[2i+2]，0 起下标）；冒泡的前部一般不满足。上面实验里堆排 2 趟后前部 (6,4,5,2,1,3)：6 ≥ 4,5；4 ≥ 2,1；5 ≥ 3——是堆；冒泡 2 趟后前部 (3,4,1,5,2,6)：3 < 4 开头就破堆序。
③ 归并 vs 希尔——整体都"半有序"
归并的有序是连续段（段长 2ᵏ）；希尔的有序是跳着的（间隔 d）。拿到状态先按段长 2、4 切一切看段内是否有序，不行再按 d = n/2、n/4 抽子序列验证。
快排的特别提醒：验证"是否可能是快排第 k 趟"时，去数满足分界性质的元素个数（左边全 ≤ 它、右边全 ≥ 它，最小/最大元素恰好在端点时也算）。第 1 趟恰好新增 1 个枢轴到位；第 2 趟在每个非空子区间再各到位 1 个——所以第 2 趟结束至少 2 个、通常 3 个。个数对不上就排除快排。
"一趟确定一个元素最终位置"清单
另一个高频问法："第一趟排序结束后，能保证有元素处于最终位置的算法是？"
| 能保证（每趟至少一个就位） | 不能保证 |
|---|---|
| 冒泡（每趟一个最值沉底/浮顶） | 直接插入、折半插入（前缀会被后来的元素继续插队） |
| 简单选择（每趟一个最小值归位） | 希尔（分组排好仍会被后续小增量打乱） |
| 快排（每趟枢轴归位） | 归并（最后一趟才全部归位） |
| 堆排（每趟堆顶归位） | 基数（按位分配，中途不看全局大小） |
记法：交换类（冒泡/快排）和选择类（简单选择/堆排）每趟必有元素到位；插入类、归并、基数都不保证。
实战演练
初始序列 (3, 8, 7, 4, 1, 5, 2, 6)，判断下列状态各是哪种排序：
问 1：(3, 8, 4, 7, 1, 5, 2, 6) 是哪种排序第 1 趟的结果？
答案
段长 2 切开：{3,8}、{4,7}、{1,5}、{2,6} 段段有序——归并排序第 1 趟。复核其他指纹：两端无全局最值聚集（排除冒泡/选择/堆排）；前缀 (3,8) 有序疑似插入 1 趟，但插入 1 趟的后部必须保持初始顺序，初始的 (…7, 4…) 在这里变成了 (…4, 7…)——排除插入。归并坐实。
问 2：(6, 4, 5, 2, 1, 3, 7, 8) 是哪种排序第 2 趟的结果？
答案
尾部 7、8 = 全局最大两个、有序就位 → 冒泡或堆排。查前部 (6,4,5,2,1,3) 堆序：6 ≥ 4,5 ✓、4 ≥ 2,1 ✓、5 ≥ 3 ✓——是大根堆，堆排序。若是冒泡，第 2 趟后前部不可能开头最大（大元素早被换走）。
问 3：(2, 1, 3, 4, 7, 5, 8, 6) 可能是快排第 1 趟的结果吗？
答案
找分界元素：3 左边 {2,1} 全 ≤ 3、右边 {4,7,5,8,6} 全 ≥ 3 ✓——3 是枢轴，可能，且 3 正是初始序列的首元素，与"取首元素为枢轴"的标准划分吻合。顺带：4 也满足分界性质（左 {2,1,3} ≤ 4、右 ≥ 4），但第 1 趟只要求至少存在一个枢轴位，多出来的"碰巧分界"不矛盾。
交互可视化
八种排序的复杂度、稳定性、特征总表（与本篇判别表互为印证）：
考研高频考点
- 给定中间状态判断排序算法（排序章选择题第一高频题型）
- 排除型："不可能是 XX 排序第 2 趟"（逐选项验证指纹）
- 快排第 k 趟后到位元素个数的下界分析
- "一趟后能确定最终位置"的算法清单（交换类/选择类 vs 插入类）
- 插入排序前缀"局部有序"与选择排序前缀"全局最小"的辨析
- 归并第 k 趟段长 2ᵏ 的推算
相关知识
- 排序算法对比与性能实测：复杂度与稳定性总表
- 快速排序：一趟划分的逐步表格，分界性质的出处
- 堆排序：堆序性质与建堆过程
- 归并排序：段长翻倍的归并过程