给我简单讲解排序算法核心知识点以及快速记忆方法：稳定性（快排/堆排/选择不稳定）、时空复杂度（最坏/最好/平均）、开放寻址与链地址法手算。

初赛（CSP-J/S 与海中自招）中，排序算法和哈希冲突是年年必出选择题的高频阵地。掌握以下体系化的口诀、对照表和手算模板，可在考场上直接秒杀。

第一部分：排序算法核心记忆法

一、稳定性口诀（秒杀判断题）

稳定性的定义：若序列中存在两个相同元素 $A_1 = A_2$，排序前 $A_1$ 在 $A_2$ 前面；若排序后 $A_1$ 必定依然在 $A_2$ 前面，则该排序算法是稳定的。

• 终极记忆口诀：

  $$\text{“考试成绩}\mathbf{不稳定}\text{就}\mathbf{快}\mathbf{选}\mathbf{对}\mathbf{C}\text{（快选堆希）}\text{”} $$
  • 快：快速排序
  • 选：简单选择排序
  • 堆：堆排序
  • 希：希尔排序（Shell Sort）

  考场规则：除了“快、选、堆、希”这 4 种跨步长/跨区间交换的算法不稳定，其余所有常见排序（冒泡、直接插入、归并、基数排序、计数排序）全部都是稳定的！

一句话直击为什么不稳定（反例）：

• 选择排序：序列 [5, 5*, 2] $\to$ 找到最小值 2，与第 1 个 5 交换 $\to$ [2, 5*, 5]，相对次序颠倒。
• 快速排序：双指针远距离交换，若遇到相同值元素极易被越过。
• 堆排序：建立大根堆/小根堆时，父子节点跨层交换调整破坏次序。
• 希尔排序：按步长分组，相同的两个元素被分到不同组别独立插入。

二、时空复杂度终极对照表

第二部分：哈希冲突手算（拉链法 vs 开放寻址）

设待插入关键字序列为：{19, 14, 23, 1, 68}，哈希表长度 $M = 11$，哈希函数为 $H(key) = key \bmod 11$。

先算各元素初始哈希地址：

• $19 \bmod 11 = 8$
• $14 \bmod 11 = 3$
• $23 \bmod 11 = 1$
• $1 \bmod 11 = 1$（冲突）
• $68 \bmod 11 = 2$

方法一：链地址法（拉链法 / 链表法）

每个哈希桶维护一个单链表（新节点通常插在表头或表尾，初赛默认按插入次序挂链）：

地址 0: 空
地址 1: -> 23 -> 1
地址 2: -> 68
地址 3: -> 14
地址 4 ~ 7: 空
地址 8: -> 19
地址 9 ~ 10: 空

考题核心计算：平均查找长度（ASL）

1. 成功查找的 ASL（ASL_succ）：

   • 查 23：比较 1 次（链表第 1 个）
   • 查 1：比较 2 次（链表第 2 个）
   • 查 68：比较 1 次
   • 查 14：比较 1 次
   • 查 19：比较 1 次
   $$\text{ASL}_{\text{succ}} = \frac{1 + 2 + 1 + 1 + 1}{5} = \frac{6}{5} = 1.2 $$

2. 失败查找的 ASL（ASL_unsucc）：
   （指查找一个不存在的数，哈希定位到该地址后需要比较到空指针的次数，分母为哈希表长 $M$）

   • 桶 1 有 2 个节点，比较 2 次后发现到链尾 NULL；
   • 桶 2、3、8 各有 1 个节点，各比较 1 次；其余 7 个桶为空（比较 0 次）：
   $$\text{ASL}_{\text{unsucc}} = \frac{2 + 1 + 1 + 1 + 0\times 7}{11} = \frac{5}{11} $$

方法二：开放寻址法（数组内挪位）

所有元素都存放在同一个大小为 $M$ 的连续数组里。通用探测公式：

1. 线性探测法（Linear Probing）

步长 $d_i = 1, 2, 3, 4, \dots$（冲突了就挨个看右边下一个位置，环形回绕）：

1. 存 19：$H=8$ 空闲，放入桶 8（比较 1 次）；
2. 存 14：$H=3$ 空闲，放入桶 3（比较 1 次）；
3. 存 23：$H=1$ 空闲，放入桶 1（比较 1 次）；
4. 存 1：$H=1$ 冲突！
   • 尝试 $(1+1) \bmod 11 = 2$，空闲，放入桶 2（比较 2 次）；
5. 存 68：$H=2$ 冲突（被 1 占了）！
   • 尝试 $(2+1) \bmod 11 = 3$，冲突（被 14 占了）；
   • 尝试 $(2+2) \bmod 11 = 4$，空闲，放入桶 4（比较 3 次）。

• 最终散列表分布： | 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | 值 | - | 23 | 1 | 14 | 68 | - | - | - | 19 | - | - | | 比较次数 | - | 1 | 2 | 1 | 3 | - | - | - | 1 | - | - |

• 查找成功的 ASL：

  $$\text{ASL} = \frac{1 + 2 + 1 + 3 + 1}{5} = \frac{8}{5} = 1.6 $$

优缺点考点：线性探测容易发生聚集（堆积）现象（Cluster），即连续一段地址被占满后，后续冲突的探测链越来越长，严重拉低性能。

2. 二次探测法（平方探测法，Quadratic Probing）

步长序列：$d_i = +1^2, -1^2, +2^2, -2^2, +3^2, -3^2, \dots$（即 $+1, -1, +4, -4, +9, -9, \dots$）

注意负数取模的手算技巧：$(-k) \bmod M = (M - (k \bmod M)) \bmod M$。
例如在 $M=11$ 时：$(2 - 1^2) \bmod 11 = 1$；$(2 - 2^2) \bmod 11 = (2 - 4) = -2 \equiv 9$。

• 二次探测核心优点：能有效缓解线性探测的聚集堆积问题，散布更均匀。