第 8 章　排序

直接插入、冒泡的比较在遇到相等关键字时即停止后移 / 不交换，一定保持 \(2_a\) 在 \(2_b\) 前；简单选择不能保持：第一趟选出最小值 1（位置 4）与位置 1 的 3 交换得 \(\{1,2_a,2_b,3\}\)——此例恰好没乱，但换 \(\{2_a,2_b,1\}\)：第一趟 1 与 \(2_a\) 交换得 \(\{1,2_b,2_a\}\)，相对序被破坏，故不稳定；快速排序同样不稳定：对 \(\{3_a,3_b,2\}\)（以首元素 3 为枢轴做一趟划分），右端的 2 填入左端空坑后，最终得 \(\{2,3_b,3_a\}\)，\(3_b\) 反超 \(3_a\)。

结论口诀（8.7 总表）：「插冒归基」稳定（直接插入、冒泡、归并、基数，外加折半插入），「希选快堆」不稳定（希尔、选择、快排、堆）。

共 7 趟（\(n-1=7\)）：

初始   (49)  38  65  97  76  13  27  49₂
第1趟  38 49   65  97  76  13  27  49₂      插 38，比较1次
第2趟  38 49 65   97  76  13  27  49₂      插 65，比较1次
第3趟  38 49 65 97   76  13  27  49₂      插 97，比较1次
第4趟  38 49 65 76 97   13  27  49₂      插 76，97 后移
第5趟  13 38 49 65 76 97   27  49₂      插 13，前面全部后移
第6趟  13 27 38 49 65 76 97   49₂      插 27
第7趟  13 27 38 49 49₂ 65 76 97       插 49₂（等于 49 时停止后移）✓

核对：最终序列 \(13,27,38,49,49_2,65,76,97\) 全局非递减 ✓，且 \(49_2\) 仍在 49 之后（该例未破坏稳定性，与「直接插入稳定」一致）。

(1) 第 \(i\) 趟在长度 \(i-1\) 的有序区中二分查找，最多比较 \(\lceil\log_2(i+1)\rceil\) 次（成功查找判定树深度）。

(2) 总计 \(\sum_{i=2}^{8}\lceil\log_2(i+1)\rceil=2+2+3+3+3+3+4=20\) 次，与输入是否有序无关；而直接插入在正序输入下只需 \(n-1=7\) 次比较——所以「输入基本有序」时直接插入反而更快，折半插入的优势在「随机 / 逆序」输入（省比较，移动照旧 \(O(n^{2})\)）。

第一趟 dk=5，子序列为按位置相差 5 的分组：\((49,13)\)、\((38,27)\)、\((65,49_2)\)、\((97)\)、\((76)\)，各组内插入排序：

dk=5： 13  27  49₂  97  76  49  38  65     ← (49↔13)(38↔27)(65↔49₂) 各组交换

第二趟 dk=3，分组：位置 \((1,4,7)\)=\(\{13,97,38\}\)、\((2,5,8)\)=\(\{27,76,65\}\)、\((3,6)\)=\(\{49_2,49\}\)，组内插入：

dk=3： 13  27  49₂  38  65  49  97  76     ← 97,38 交换；76,65 交换

第三趟 dk=1，就是一趟直接插入（此时序列已基本有序，只有少量元素需移动：38、49、76 各插一次）：

dk=1： 13  27  38  49  49₂  65  76  97     ✓

核对：三趟后全局有序 ✓。注意 dk=3 趟后 \(49_2\)（位置 3）仍在 49（位置 6）之前，但最终结果 \(49_2\) 排在 49 之后——相等元素的相对次序被改变，希尔排序不稳定的直接证据。

初始   49  38  65  97  76  13  27  49₂
第1趟  38  49  65  76  13  27  49₂ | 97     97 沉底（交换 5 次）
第2趟  38  49  65  13  27  49₂ | 76  97
第3趟  38  49  13  27  49₂ | 65  76  97
第4趟  38  13  27  49₂ | 49  65  76  97    49₂ 与 49 相等不交换（稳定的体现）
第5趟  13  27  38 | 49  49₂  65  76  97
第6趟  全趟无交换 → 提前结束                    ✓

性能：最好 \(O(n)\)（正序，一趟检出），最坏 / 平均 \(O(n^{2})\)（逆序比较 \(\frac{n(n-1)}{2}\) 次）；移动均为元素交换（3 次赋值 / 次）；空间 \(O(1)\)；稳定（相邻相等不交换）。

第 1 趟对全区间划分（过程见图 8-1）：枢轴 49 挖出 → 27 填左坑 → 65 填右坑 → 13 填左坑 → 97 填右坑 → 相遇于位置 4 → 49 入位：

第1趟  27  38  13 [49] 76  97  65  49₂    枢轴 49 → 最终位置 4
第2趟  13 [27] 38  49   76  97  65  49₂    左段枢轴 27 → 位置 2
第3趟  13  27  38  49   49₂ 65 [76] 97     右段枢轴 76 → 位置 7
第4趟  13  27  38  49  [49₂] 65  76  97    段 {49₂,65} 枢轴 49₂ → 位置 5（本趟无移动）✓

递归树（每个结点是一次划分的区间）：

[1..8]枢轴49
 ├─[1..3]枢轴27        └─[5..8]枢轴76
 │   ├─[1..1]13         ├─[5..6]枢轴49₂   └─[8..8]97
 │   └─[3..3]38             ├─[5..5]  └─[7..7]65（单元素区间不再划分）

核对：最终 \(13,27,38,49,49_2,65,76,97\) 有序 ✓。注意 \(49_2\) 最终排到 49 之后而初始在其前——快排不稳定的证据。

技巧：快排一趟后必存在一个「枢轴位」\(i\)：\(a[i]\) 左边全部 ≤ 它、右边全部 ≥ 它。逐项检验每个位置是否可能是枢轴位：

A：逐个排除——41 右侧有 24 ✗；58 右侧有 5 ✗；63 右侧有 5 ✗；90 右侧有 5 ✗；24/30/12 左侧有 41、5 左侧有 41 ✗。无候选，不可能。

B：末位 90 是最大值，左边全部 ≤ 90 ✓——可作为枢轴位（例如初始序列 \(\{90,12,24,30,41,58,63,5\}\) 一趟划分结果恰为 B），可能。

C：41 右侧有 30 ✗；30 左侧有 41 ✗；90 右侧有 63、58 ✗；其余位置左侧均有更大值 ✗。不可能。

D：逆序，任何位置左侧含 90、右侧含 5，两头都不满足 ✗（顺带记忆：正序 / 逆序正是快排最坏输入）。不可能。

故选 B。

(1) 第 \(i\) 趟在长度 \(n-i+1\) 的无序区比较 \(n-i\) 次，总计固定为 \[ \sum_{i=1}^{n-1}(n-i)=\frac{n(n-1)}{2}=\frac{8\times7}{2}=28\ \text{次} \] ——与初始序列无关（正序、逆序都比 28 次），这一点常被直接考查。

(2) 每趟至多 1 次交换（3 次移动）：最好（正序）移动 0 次，最坏移动 \(3(n-1)\) 次。时间恒为 \(O(n^{2})\)，空间 \(O(1)\)，不稳定（跨越式交换可破坏相等元素相对序，反例见例 1 的 \(\{2_a,2_b,1\}\)）。对 \(\{49,38,65,97,76,13,27,49_2\}\)：第 1 趟 13↔49、第 2 趟 27↔38、……第 7 趟得 \(13,27,38,49,49_2,65,76,97\) ✓。

(1) 从 \(i=\lfloor 8/2\rfloor=4\) 到 1 依次筛选（对照图 8-2）：

筛选结点4（97）：孩子 49₂，97 ≥ 49₂ → 不动
筛选结点3（65）：孩子 13、27，均小于 65 → 不动
筛选结点2（38）：大孩子 97 > 38 → 交换；继续：孩子 49₂ > 38 → 交换
        49  97  65  49₂ 76  13  27  38
筛选结点1（49）：大孩子 97 > 49 → 交换；大孩子 76 > 49 → 交换
建堆完成： 97  76  65  49₂ 49  13  27  38      ✓（每个结点 ≥ 孩子）

(2) 每趟「堆顶 ↔ 无序区末尾交换，再筛堆顶」：

第1趟  76  49₂ 65  38  49  13  27 | 97      （97 到位）
第2趟  65  49₂ 27  38  49  13 | 76  97      （76 到位）
第3趟  49  49₂ 27  38  13 | 65  76  97      （65 到位）
……继续 5 趟后：13 27 38 49 49₂ 65 76 97      ✓

要点：建堆时间 \(O(n)\)；每趟筛选 \(O(\log_2 n)\)，共 \(n-1\) 趟 → 堆排序最好 / 平均 / 最坏均为 \(O(n\log_2 n)\)，空间 \(O(1)\)，不稳定（跨越式交换，49₂ 与 49 相对序已变）。

(1) 插入：新元素放在堆尾（位置 7），再向上与双亲比较（「上浮」）：60 的双亲是 53 → 60 > 53 交换；再与 91 比较 → 60 < 91 停止。结果 \[ (91,\,60,\,72,\,44,\,24,\,65,\,53) \] 2 次比较，时间 \(O(\log_2 n)\)。

(2) 删除：堆顶 91 出堆，堆尾元素 53 补到堆顶，再向下筛选：孩子 60、72 中取大者 72 → 53 < 72 交换；孩子 65 → 53 < 65 交换；无孩子停止。结果 \[ (72,\,60,\,65,\,44,\,24,\,53) \] 共 3 次比较（2 次选大孩子之外的比较：根层 2 次 + 结点 3 层 1 次），时间 \(O(\log_2 n)\)。

结论：插入上浮、删除下沉，两者都只沿一条根—叶路径操作，故都是 \(O(\log_2 n)\)——这是选择题高频答案。

初始    (49)(38)(65)(97)(76)(13)(27)(49₂)   8 个长度 1 的段
第1趟   (38 49)(65 97)(13 76)(27 49₂)        段长 1→2
第2趟   (38 49 65 97)(13 27 49₂ 76)          段长 2→4
第3趟   (13 27 38 49 49₂ 65 76 97)           段长 4→8  ✓

每趟段长翻倍，从 1 到 \(n\) 需要 \(\lceil\log_2 n\rceil\) 趟：\(n=8\to\lceil\log_2 8\rceil=3\) 趟 ✓；若 \(n=100\)，则需 \(\lceil\log_2 100\rceil=7\) 趟。

性能：每趟全体元素恰被扫描一次 \(O(n)\)，共 \(O(\log_2 n)\) 趟 → 最好 / 平均 / 最坏均为 \(O(n\log_2 n)\)；空间 \(O(n)\)（辅助数组 B）；稳定（Merge 中 \(a[i]\le a[j]\) 时优先取左段，相等不越过）；归并是外部排序的基础（8.5.3）。注意：归并比较次数与初始序列有关（介于 \(\lceil n/2\rceil\log_2 n\) 与 \((n-1)\log_2 n\) 量级之间）。

第 1 趟按个位分配（队列内保持到达顺序）：Q₃←13；Q₅←65；Q₆←76；Q₇←97,27；Q₈←38；Q₉←49,49₂。收集（Q₀→Q₉ 依次）： \[ 13,\ 65,\ 76,\ 97,\ 27,\ 38,\ 49,\ 49_2 \]

第 2 趟按十位分配：Q₁←13；Q₂←27；Q₃←38；Q₄←49,49₂；Q₆←65；Q₇←76；Q₉←97。收集： \[ 13,\ 27,\ 38,\ 49,\ 49_2,\ 65,\ 76,\ 97\quad ✓ \] （\(49_2\) 与 49 同入 Q₄ 且保持先来在前——队列先进先出保证稳定。）

性能：每趟分配 \(n\) 次、收集 \(n+r\) 次（\(r\) 个队列依次接起来），共 \(d\) 趟：时间 \(O(d(n+r))\)，与 \(n\log_2 n\) 无关；空间 \(O(r)\)（\(r\) 个队列）；适合位数少（\(d\) 小）而取值范围大（\(r^{d}\) 大）的关键字，如整数不比较却胜过比较类排序的典型场景；若关键字位数多（\(d\) 大）则反而不划算。

B。快排每趟划分后枢轴左边全部 ≤ 它、右边全部 ≥ 它，枢轴此后不再移动，处于最终位置。A 只形成局部有序前缀（例 2 第 4 趟的 76 后被 13、27 顶到后面）；C 只把段长翻倍（例 11 第 1 趟的 38、49 之后还会被拆开重排）；D 只保证各增量子序列有序（例 4 第一趟后 13 在位置 1，看似就位纯属巧合，不保证）。
同类真题常把「冒泡 / 简单选择 / 堆 / 快排」打包为正确选项组合，务必对应 warn-box 默写。