数据结构期末考前救急

1 模式匹配

1.1 核心解题步骤

构建分析表格
需创建4行多列表格，列数=关键字个数+1（预留补充列），各行含义如下：
- 第1行（下标）：从0开始依次递增（如关键字有10个，下标为0~9）；
- 第2行（关键字）：直接复制题目给定的字符序列（如"ababacaaad"）；
- 第3行（next数组）：前两个值固定，next[0] = -1，next[1] = 0，后续值需计算；
- 第4行（nextval数组）：nextval[0] = -1，后续值根据next值和关键字推导。
计算next数组
对下标i ≥ 2，比较当前关键字T[i]前的子串与字符串起始子串的最长相等前缀后缀长度：
- 规则：若T[i]前k个字符与起始k个字符相等，且k是最大可能值，则next[i] = k；若无相等子串，next[i] = 0。
- 例题：已知T = "ababacaaad"，计算next[3]（T[3] = 'b'）：
  1. i=3，前子串为T[1..2] = "ba"；
  2. 对比起始子串T[0..1] = "ab"（不相等）；
  3. 缩小范围，对比前1个字符T[2] = "a"与起始1个字符T[0] = "a"（相等）；
  4. 故next[3] = 1。
计算nextval数组
对每个下标i，根据next[i] = k判断：
- 若T[i] == T[k]，则nextval[i] = nextval[k]；相同则延续上一个的nextval
- 若T[i] != T[k]，则nextval[i] = k。不同则直接使用自己的next值
- 例题：延续上述T，计算nextval[2]（T[2] = 'a'）：
  1. next[2] = 0，T[2] = 'a'，T[0] = 'a'（相等）；
  2. 故nextval[2] = nextval[0] = -1。

2 二叉树构建与线索化

2.1 基于遍历序列构建二叉树

2.1.1 中序+后序遍历构建

核心规则：
1. 后序遍历的最后一个元素是二叉树的根节点；
2. 在中序遍历中找到根节点的位置，根左侧所有元素为左子树节点，右侧所有元素为右子树节点；
3. 递归对左、右子树执行上述步骤，直至子树节点为空。

2.1.2 前序+中序遍历构建

核心规则：
1. 前序遍历的第一个元素是二叉树的根节点；
2. 中序遍历中根节点左侧为左子树，右侧为右子树；
3. 递归构建左、右子树（前序中左子树节点为根后连续k个元素，k为中序左子树节点个数）。

2.2 中序线索二叉树

核心逻辑：中序遍历顺序为“左→根→右”，对无左孩子的节点，左指针指向中序前驱；对无右孩子的节点，右指针指向中序后继（前驱/后继为中序遍历中相邻的节点）。
例题：对2.1.1构建的二叉树进行中序线索化：
1. 中序遍历序列：a→b→c→d→e→f→g→h→i；
2. a无左孩子，左指针为NULL（无前驱），右指针指向后继b；
3. b有左孩子a（无需线索），无右孩子，右指针指向后继c；
4. c无左孩子，左指针指向前驱b，无右孩子，右指针指向后继d；
5. 以此类推，直至所有无孩子节点完成线索化。

3 树的节点个数计算（以度为3的树为例）

3.1 核心公式

节点总数公式：
树的节点总数等于所有不同度数节点的个数之和：
$$n = n_0 + n_1 + n_2 + n_3$$
其中：
- $n_0$：度为0的节点数（叶子节点数）；
- $n_1$：度为1的节点数；
- $n_2$：度为2的节点数；
- $n_3$：度为3的节点数。
节点度数关系公式：
所有节点的度数之和加1（根节点无父节点）等于节点总数：
$$n = 0 \times n_0 + 1 \times n_1 + 2 \times n_2 + 3 \times n_3 + 1$$

3.2 例题

已知某度为3的树中，$n_2 = 200$，$n_3 = 100$，求叶子节点数$n_0$：

联立两个公式：
- 公式1：$n = n_0 + n_1 + 200 + 100 = n_0 + n_1 + 300$；
- 公式2：$n = 0 \times n_0 + 1 \times n_1 + 2 \times 200 + 3 \times 100 + 1 = n_1 + 701$；
两式相等消去$n_1$：
$n_0 + n_1 + 300 = n_1 + 701$ → $n_0 = 401$。

4. 二叉排序树 (BST) 复习笔记

4.1 构建规则

核心原则：左孩子 < 根节点 < 右孩子

根节点确定：序列中第一个元素作为根。
插入逻辑：
- 若元素值 > 当前节点值 $\rightarrow$ 往右子树走；
- 若元素值 < 当前节点值 $\rightarrow$ 往左子树走；
终止条件：直到找到叶子节点的左/右空位置（NULL），将新元素放入该位置。

4.2 例题：构建与查找分析

题目：已知关键字序列 K = {34, 76, 45, 18, 26, 54, 92, 38}。

1. 构建过程图解

34 为根。
76 > 34 (右)。
45 > 34 (右) $\rightarrow$ < 76 (左)。
18 < 34 (左)。
26 < 34 (左) $\rightarrow$ > 18 (右)。
54 > 34 $\rightarrow$ < 76 $\rightarrow$ > 45 (右)。
92 > 34 $\rightarrow$ > 76 (右)。
38 > 34 $\rightarrow$ < 76 $\rightarrow$ < 45 (左)。

最终树结构：

      34 (L1)
     /  \
(L2)18   76
     \   /  \
(L3) 26 45   92
       /  \
(L4)  38   54

2. 查找次数计算

查找 54（存在）：
- 路径：34 $\rightarrow$ 76 $\rightarrow$ 45 $\rightarrow$ 54
- 比较次数：4次。
查找 100（不存在）：
- 路径：34 $\rightarrow$ 76 $\rightarrow$ 92 $\rightarrow$ NULL
- 比较次数：3次（比较至92后，发现应往右走但为空，确定失败）。

3. 平均查找长度 (ASL) 计算

① 查找成功 ($ASL_{success}$)

公式：$\sum(本层节点数 \times 层数) / 节点总数$
统计：
- 第1层：1个 (34)
- 第2层：2个 (18, 76)
- 第3层：3个 (26, 45, 92)
- 第4层：2个 (38, 54)
计算：
$$ASL_{success} = \frac{1 \times 1 + 2 \times 2 + 3 \times 3 + 4 \times 2}{8} = \frac{22}{8} = 2.75$$

② 查找不成功 ($ASL_{unsuccess}$) —— 重点/难点

方法：补坑法。统计所有空指针（NULL）及其父节点的层数。
总失败情况：$n + 1 = 9$ 个空指针。
统计过程：
- 第2层空指针：节点18的左孩子 (1个) $\rightarrow$ 比较 2 次
- 第3层空指针：节点26左右、节点92左右 (4个) $\rightarrow$ 比较 3 次
- 第4层空指针：节点38左右、节点54左右 (4个) $\rightarrow$ 比较 4 次
计算：
$$ASL_{unsuccess} = \frac{1\times2 + 4\times3 + 4\times4}{9} = \frac{2 + 12 + 16}{9} = \frac{30}{9} \approx 3.33$$

4.3 节点的删除操作

删除节点 p 后，必须保持二叉排序树的有序性。

节点情况	操作方法
叶子节点 (度0)	直接删除，修改父节点指针为 NULL
单孩子节点 (度1)	子承父业。让 p 的唯一孩子直接顶替 p 的位置
双孩子节点 (度2)	找替身（转变为删度0或度1节点的问题）。 1. 找后继：p 的右子树中的最左节点（最小值）。 2. 找前驱：p 的左子树中的最右节点（最大值）。 3. 用替身的值覆盖 p，然后删除替身节点。

示例：在原树中删除 76

76 有两个孩子 (45, 92)。
方案 A (找后继)：右子树 (92…) 最小是 92。用 92 覆盖 76，删除原来的 92。
方案 B (找前驱)：左子树 (45…) 最大是 54。用 54 覆盖 76，删除原来的 54。

5 广义表

5.1 核心概念计算

概念	计算规则	例题（广义表`L = (a, (b), (c, (d,e,f)))`）
表头	最外层括号内第一个逗号前的内容（含内层括号，若有）	表头 = `a`
表尾	去掉表头后，剩余内容外层加括号（表尾必为广义表）	表尾 = `((b), (c, (d,e,f)))`
长度	最外层元素的个数（每个可为原子或广义表，不嵌套计数）	长度 = 3（`a`、`(b)`、`(c, (d,e,f))`）
深度	嵌套括号的最大层数（含最外层括号，原子深度为0，广义表深度为子表最大深度+1）	深度 = 3（最内层`(d,e,f)`深度为2，加最外层共3）

5.2 存储结构画法

节点规则：用方框表示节点，1代表广义表，0代表原子；并列节点用箭头连接，最后一个节点箭头指向NULL。
例题：广义表(a, (b), (c, (d,e,f)))的存储结构：
1. 最外层为广义表节点（1），连接3个并列节点；
2. 第一个节点：原子a（0,a），箭头指向第二个节点；
3. 第二个节点：广义表(b)（1），内部连接原子b（0,b），箭头指向第三个节点；
4. 第三个节点：广义表(c, (d,e,f))（1），内部连接原子c（0,c）和广义表(d,e,f)（1），箭头指向NULL；
5. 广义表(d,e,f)（1）内部连接3个原子d、e、f（均为0），最后一个原子箭头指向NULL。

6 数组存储地址计算

6.1 核心公式

对于m行n列的二维数组（下标从1开始），元素a[i][j]的存储地址（顺序存储，行优先）：
$$LOC(a[i][j]) = LOC(a[1][1]) + [(i-1) \times n + (j-1)] \times k$$
其中：

$LOC(a[1][1])$：数组首元素的存储地址；
$i,j$：目标元素的行、列下标；
$n$：数组的列数；
$k$：每个元素占用的存储单元数（如int类型k=4）。

6.2 例题

已知二维数组A[1..3][1..4]（3行4列），首地址LOC(A[1][1]) = 2000，每个元素占2个单元，求LOC(A[2][3])：

代入公式：
- $i=2$，$j=3$，$n=4$，$k=2$，$LOC(a[1][1])=2000$；
- 计算过程：
  $$LOC(A[2][3]) = 2000 + [(2-1) \times 4 + (3-1)] \times 2 = 2000 + (4 + 2) \times 2 = 2012$$

7 二叉树相关代码设计

7.1 求二叉树节点总数

// 二叉树节点结构（假设数据为int类型）
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 递归求节点总数：空树返回0，非空则左子树+右子树+当前节点
int countNodes(TreeNode *b) {
    if (b == NULL) return 0;
    else return countNodes(b->left) + countNodes(b->right) + 1;
}

7.2 求二叉树高度

// 递归求高度：空树高度为0，非空则取左/右子树最大高度+1
int treeHeight(TreeNode *b) {
    int leftH, rightH;
    if (b == NULL) return 0;
    else {
        leftH = treeHeight(b->left);  // 左子树高度
        rightH = treeHeight(b->right); // 右子树高度
        return (leftH > rightH) ? (leftH + 1) : (rightH + 1);
    }
}

7.3 输出二叉树叶子节点

// 叶子节点：左右子树均为空，递归遍历输出
void printLeaves(TreeNode *b) {
    if (b != NULL) {
        if (b->left == NULL && b->right == NULL) {
            printf("%d ", b->data);  // 输出叶子节点值
        }
        printLeaves(b->left);   // 遍历左子树
        printLeaves(b->right);  // 遍历右子树
    }
}

8 哈弗曼树与编码

8.1 哈弗曼树构建规则

初始：将所有给定权重（如字符出现频率）作为独立的叶子节点；
迭代：每次选择两个权重最小的节点，构建新节点（新节点权重=两节点权重之和）；
更新：删除原两个节点，将新节点加入节点集合；
终止：直至节点集合中只剩一个节点（根节点），哈弗曼树构建完成。

8.2 例题：构建与编码

已知权重[2,3,6,7,10,19,21,32]，构建哈弗曼树并生成编码（左子树记为0，右子树记为1）：

构建过程：
- 第1轮：选2、3→新节点5；剩余[5,6,7,10,19,21,32]；
- 第2轮：选5、6→新节点11；剩余[7,10,11,19,21,32]；
- 第3轮：选7、10→新节点17；剩余[11,17,19,21,32]；
- 第4轮：选11、17→新节点28；剩余[19,21,28,32]；
- 第5轮：选19、21→新节点40；剩余[28,32,40]；
- 第6轮：选28、32→新节点60；剩余[40,60]；
- 第7轮：选40、60→新节点100（根）；构建完成。
哈弗曼编码：
- 权重2（字符c）：路径100→60→28→11→5→2→编码10000；
- 权重7（字符a）：路径100→60→28→17→7→编码1010；
- 权重19（字符b）：路径100→40→19→编码00。

8.3 带权路径长度 (WPL)

这是考试最爱问的计算题。
公式：$WPL = \sum (\text{叶子权值} \times \text{路径长度})$

路径长度：从根到叶子经过了几根线（或者看编码有几位）。
计算本题 WPL：
- C(2), F(3): 5层 $\to (2+3) \times 5 = 25$
- D(6), A(7), H(10): 4层 $\to (6+7+10) \times 4 = 92$
- E(32): 2层 $\to 32 \times 2 = 64$
- B(19), G(21): 2层 $\to (19+21) \times 2 = 80$
- Total WPL = $25 + 92 + 64 + 80 = \mathbf{261}$

速算技巧：WPL 也等于所有非叶子节点的权值之和。
本题非叶子节点有：5, 11, 17, 28, 40, 60, 100。
$5+11+17+28+40+60+100 = 261$。

9 最小生成树

9.1 Prim算法（从节点出发）

核心思想：从指定起始节点开始，逐步将“已选节点集”与“未选节点集”之间权值最小的边对应的节点加入已选集，避免环路，直至所有节点加入。
例题：图节点0~5，边权重(0,1)=1、(0,2)=5、(0,3)=2、(1,2)=3、(1,4)=4、(2,5)=6、(3,5)=8、(4,5)=4，从0出发构建：
1. 初始已选{0}，选边(0,1)=1→已选{0,1}；
2. 选边(0,3)=2→已选{0,1,3}；
3. 选边(1,2)=3→已选{0,1,3,2}；
4. 选边(2,5)=6→已选{0,1,3,2,5}；
5. 选边(4,5)=4→已选{0,1,3,2,5,4}；
6. 最小生成树边集：{(0,1),(0,3),(1,2),(2,5),(4,5)}，总权重1+2+3+6+4=16。

9.2 Kruskal算法（从边出发）

核心思想：按边权重从小到大排序，每次选权重最小的边，若不构成环路则保留，直至边数=节点数-1（无环路的连通图）。
例题（同9.1的图）：
1. 边按权重排序：(0,1)=1、(0,3)=2、(1,2)=3、(1,4)=4、(4,5)=4、(2,5)=6、(3,5)=8；
2. 依次选边：(0,1)（无环）→(0,3)（无环）→(1,2)（无环）→(4,5)（无环）→(2,5)（无环）；
3. 边数=5（节点数6-1），停止，结果与Prim算法一致。

10 图的遍历

10.1 深度优先遍历（DFS）

核心规则：从起始节点出发，优先访问当前节点的未访问邻接节点，深入到无法继续时回溯，直至所有节点访问完毕（类似“走迷宫优先探到底”）。
例题：图结构1-2-3-4、1-5、1-6（节点1与2、5、6相连，2与3相连，3与4相连），从1出发：
- 遍历路径1：1→2→3→4→5→6（访问1后先探2，再探3、4；回溯1后探5，最后探6）；
- 遍历路径2：1→5→2→3→4→6（邻接节点选择顺序不同，路径可变化，但均为深度优先）。

10.2 广度优先遍历（BFS）

核心规则：从起始节点出发，先访问当前节点的所有未访问邻接节点（按“层”访问），再依次访问邻接节点的未访问邻接节点（类似“水波扩散”）。
例题（同10.1的图）：
- 遍历路径：1→2→5→6→3→4（先访问1的邻接节点2、5、6；再访问2的邻接节点3；最后访问3的邻接节点4）。

我们将哈希冲突的处理方法分为两大类：

开放定址法（Open Addressing）：包括线性探测、二次探测。
链地址法（Chaining）：即拉链法。

一、线性探测法 (Linear Probing)

“挨个找车位”

1. 原理

当计算出的哈希地址 $H(key) = d$ 被占用时，就去检查下一个位置 $d+1$，如果还被占，就检查 $d+2$，直到找到一个空位置为止。

公式：$H_i = (H(key) + i) % m$ （$m$ 为表长，$i = 1, 2, 3…$）
注意：这是一种循环探测。如果查到了表尾（$m-1$），下一个探测位置是表头（$0$）。

2. 核心考点：堆积（Clustering）现象

这是线性探测法最大的缺点。

现象：因为冲突的元素都被挤到了相邻的位置，形成了一大片连续的“非空区域”。
后果：后来的元素（即使它们的哈希值本来不冲突），一旦撞进这个区域，也得一路往后找，导致冲突概率像滚雪球一样越来越大，大大降低了查找效率。

3. 示例简述

表长 5，H(key)=key%5。
插入 5：放下标 0。
插入 10：0 被占 $\to$ 找 1 (空)，放入。
插入 11：1 被占 $\to$ 找 2 (空)，放入。
查找 11：先去 1，不是 11；再去 2，是 11。比较 2 次。

二、二次探测法 (Quadratic Probing)

“跳着找车位”

1. 原理

为了解决线性探测的“堆积”问题，二次探测法在冲突时不挨个找，而是双向跳跃式寻找。

增量序列：$1^2, -1^2, 2^2, -2^2, 3^2, -3^2 …$
公式：
- 第 1 次冲突：$d_1 = (H(key) + 1^2) % m$
- 第 2 次冲突：$d_2 = (H(key) - 1^2) % m$
- 第 3 次冲突：$d_3 = (H(key) + 2^2) % m$
- …
- 第 $i$ 次冲突：$d_i = (H(key) \pm k^2) % m$

2. 举例演示（必看）

设表长 $m=13$，关键码 $key=14$，哈希函数 $H(key) = key % 13 = 1$。
假设下标 1 已经被占了。

线性探测会找：2, 3, 4…
二次探测的寻找路径：
1. +1²：$(1 + 1) % 13 = 2$。若 2 被占，则：
2. -1²：$(1 - 1) % 13 = 0$。若 0 被占，则：
3. +2²：$(1 + 4) % 13 = 5$。若 5 被占，则：
4. -2²：$(1 - 4) % 13 = -3$ $\rightarrow$ 注意负数取模：$13-3=10$。

3. 优缺点

优点：能较好地避免“堆积”现象（只有哈希值相同的元素才会走同一条探测路径）。
缺点：计算稍麻烦；可能会出现“表里明明有空位，但跳来跳去就是跳不到空位”的情况（为了避免这个，表长 $m$ 通常取 $4k+3$ 形式的素数）。

三、链地址法 (Chain Address / 拉链法)

“无限深抽屉”

1. 原理

不把冲突的元素硬塞到别人的位置里，而是把哈希表看作一个指针数组。
所有哈希地址为 $i$ 的元素，都挂在下标为 $i$ 的单链表中。

2. 结构图示

设 $H(key) = key % 13$。序列：{1, 14, 27, 2}

$1 % 13 = 1$
$14 % 13 = 1$
$27 % 13 = 1$
$2 % 13 = 2$

结构如下：

下标
[0] -> NULL
[1] -> 27 -> 14 -> 1 -> NULL  (冲突的都在这串链表上)
[2] -> 2 -> NULL
[3] -> NULL
...

(注：新元素通常可以用“头插法”插入链表，比较快)

3. 链地址法的 ASL 计算（与开放定址法完全不同！）

例题：上述链表结构中，求查找成功的 ASL。

第 1 层节点（27, 2）：比较 1 次就能找到。共 2 个。
第 2 层节点（14）：比较 2 次。共 1 个。
第 3 层节点（1）：比较 3 次。共 1 个。
总数 $n = 4$。

$$ASL_{成功} = \frac{1\times2 + 2\times1 + 3\times1}{4} = \frac{7}{4} = 1.75$$

4. 优缺点（高频考点）

优点：
1. 无堆积：非同义词（Hash值不一样的）决不会发生冲突。
2. 删除简单：直接在链表上删节点即可（开放定址法通常不能物理删除，只能标记为“已删除”，否则会截断后续元素的探测路径）。
3. 空间弹性大：适合无法确定元素个数的情况。
缺点：
1. 指针占用额外的空间。

四、三种方法的终极对比（考前背诵）

特性	线性探测法	二次探测法	链地址法（拉链法）
冲突处理	$d+1, d+2, …$	$d+1^2, d-1^2, d+2^2…$	挂链表
堆积现象	严重	较轻	无
查找效率	最差（因为堆积）	中等	最高
空间利用	容易填满，装填因子不能太大	同左	需额外指针空间，但可存更多元素
删除操作	困难（需用逻辑标记）	困难	简单（链表删除）
ASL计算	累加探测次数 / $n$	同左	$\sum(层数 \times 个数) / n$

看到“线性探测”：画表格，注意不要算错下标，注意循环回表头。
看到“二次探测”：如果算出来是负数，记得加上表长 $m$ 变正数。
看到“链地址”：ASL 计算时，是算链表的深度，别用线性探测的方法算。
取余的除数是谁？
- 公式 $H(key) = key % p$。如果题目给了 $p$ 就用 $p$；没给 $p$ 就直接用表长 $m$。
- 陷阱：有些题目表长 $m=16$，但要求 $p=13$（最大素数）。一定要看清题意。
分母不要搞错！
- 算成功 ASL：分母是元素个数 (有多少个数据)。
- 算不成功 ASL：分母是表长 (有多少个坑位)。
循环边界
- 线性探测查到表尾（下标12）还没停，下一步是回到下标0，不是停止！
不成功的计算逻辑
- 一定要数到**空位置（NULL）**为止，包括那个空位置本身也算一次比较。

12 排序 (Sorting)

12.1 基本概念

稳定性：若待排序表中存在两个关键字相同的元素 $R_i$ 和 $R_j$ ($R_i=R_j$)，排序后它们的相对位置保持不变，则称算法是稳定的；否则为不稳定。
- 口诀：快（速）、希（尔）、选（择）、堆（排）是不稳定的。
内/外排序：
- 内排序：数据全部在内存中进行。
- 外排序：数据量太大，需要在内存和外存之间移动（如磁盘排序）。

12.2 插入排序 (Insertion Sort)

1. 直接插入排序 (Direct Insertion Sort)

核心思想：类似打扑克牌。将待排序元素插入到前面已排好序的子序列中。
规则：
1. 第 1 趟：认为第 1 个元素有序。
2. 第 $i$ 趟：将第 $i+1$ 个元素插入到前 $i$ 个有序序列的适当位置。
考点：
- 最好情况：输入已有序，复杂度 $O(n)$。
- 最坏情况：输入逆序，复杂度 $O(n^2)$。
例题演示：[34, 50, 25]
- 初始：[34], 50, 25
- 插入50：[34, 50], 25
- 插入25：[25, 34, 50]

2. 希尔排序 (Shell Sort)

核心思想：缩小增量排序。先将序列按增量 $d$ 分组，组内进行直接插入排序，然后缩小 $d$ 直至 1。
规则：
- 跳跃式比较和移动。
- 最后一步一定是 $d=1$ 的直接插入排序。
考点：
- 不稳定（因为跳跃交换）。
- 适合初期让原本无序的序列基本有序。

12.3 交换排序 (Exchange Sort)

1. 冒泡排序 (Bubble Sort)

核心思想：两两比较，反序则交换。每趟将一个“最大”的元素“沉底”。
规则：
- 若一趟排序中没有发生交换，说明序列已有序，算法提前结束。
考点：
- 第 $i$ 趟结束，倒数第 $i$ 个元素归位（全局最大/小）。
- 稳定。

2. 快速排序 (Quick Sort) —— ★ 重中之重

核心思想：分治法。
1. 基准：选一个元素（通常是第一个）作为 Pivot。
2. 分区：比 Pivot 小的放左边，比 Pivot 大的放右边。
3. 递归：对左右两边继续排。
例题：序列 [34, 50, 25, 23, 56, 20]，基准 34。
- 分区过程：
  - L指向34，R指向20。20 < 34，20移到L位置 [20, 50, 25, 23, 56, (20)]。
  - L右移找大：50 > 34，50移到R位置 [20, (50), 25, 23, 56, 50]。
  - R左移找小：23 < 34，23移到L位置 [20, 23, 25, (23), 56, 50]。
  - L右移找大：25 < 34，继续；碰到R。
  - 将 34 填入相遇点。
- 结果：[20, 23, 25, 34, 56, 50]。
考点：
- 平均性能最优：$O(n\log n)$。
- 最坏情况：序列已有序（正序或逆序），退化为冒泡 $O(n^2)$。
- 空间复杂度：需要递归栈 $O(\log n)$。

12.4 选择排序 (Selection Sort)

1. 简单选择排序 (Simple Selection Sort)

核心思想：在无序区中选出最小的元素，与无序区的第一个元素交换。
规则：
- 无论输入是否有序，比较次数恒为 $n(n-1)/2$。
考点：
- 不稳定。例：序列 [2, 2', 1]，第一趟 1 和 2 交换 $\rightarrow$ [1, 2', 2]，两个 2 相对位置变了。

2. 堆排序 (Heap Sort) —— 难点

前置概念：
- 大顶堆：根 $\ge$ 左右孩子（数组看起来是乱的，但逻辑结构满足堆定义）。
步骤：
1. 建堆：从最后一个非叶子节点开始，自下而上调整。
2. 排序：输出堆顶元素（与末尾交换），剩余元素重新调整为堆。
考点：
- 空间复杂度低：$O(1)$，不需要像归并那样开额外数组。
- 时间复杂度恒为 $O(n\log n)$。
- 适合从海量数据中选出前 $K$ 个最大/最小的数。

12.5 归并排序 (Merge Sort)

核心思想：分治与合并。将两个有序表合并成一个有序表（2-路归并）。
步骤：
- 初始视作 $n$ 个长度为 1 的有序子序列。
- 两两合并，得到 $\lceil n/2 \rceil$ 个长度为 2 的序列…
考点：
- 空间复杂度最高：$O(n)$，需要辅助数组。
- 稳定且效率高。

12.6 核心对比表（★背诵★）

排序算法	平均时间	最好时间	最坏时间	空间	稳定性	备注
直接插入	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定	序列基本有序时最快
希尔排序	$O(n^{1.3})$	-	$O(n^2)$	$O(1)$	不稳定	增量分组
冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定	没交换就停止
快速排序	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	$O(\log n)$	不稳定	综合性能最好
简单选择	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定	比较次数固定
堆排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	不稳定	适合选Top K
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	稳定	占内存

12.7 考试解题方法论

题型一：手写排序过程

题目问法：“请写出使用XX排序算法进行第3趟排序后的结果。”

直接插入：数前 3 个数，把它们排好序，后面的完全不动。
冒泡排序：看最后 3 个数，把最大的 3 个找出来放到最后（有序区在尾部）。
简单选择：看前 3 个数，把最小的 3 个找出来放到前面（有序区在头部）。
快速排序：
- 这也是最容易错的。切记基准（Pivot）归位。
- 画图法：画两个指针，左边找大，右边找小，填坑。
- 检查标准：基准归位后，左边的都比它小，右边的都比它大。

题型二：排序算法的选择

题目问法：“数据基本有序，选什么？数据量极大，选什么？”

若 $n$ 较小：直接插入排序，简单选择排序。
若数据基本有序：直接插入排序（最快）、冒泡排序。
- 避坑：此时快速排序最慢！
若 $n$ 较大：快速排序、堆排序、归并排序。
- 要求稳定 $\rightarrow$ 归并。
- 内存空间紧张 $\rightarrow$ 堆排。
- 追求平均速度 $\rightarrow$ 快排。

题型三：复杂度与稳定性判断

记忆口诀：

稳定性：“快希选堆”不稳定（心情不稳定：快些选一堆朋友去玩）。
空间：快排 $\log n$（递归），归并 $n$（辅助），其他 $1$。
时间：
- $O(n^2)$ 组：插、冒、选。
- $O(n\log n)$ 组：快、归、堆。

模拟练习

题目：有一组数据 [12, 2, 16, 30, 28, 10, 16*, 20, 6, 18]，使用某种排序后，变成了 [2, 6, 10, 12, 16, 16*, 18, 20, 28, 30]（注意两个16的相对位置没变）。
请问下列哪种算法不可能是它使用的算法？
A. 冒泡排序
B. 快速排序
C. 归并排序
D. 直接插入排序

👉 点击查看解析

**答案：B** **解析**：题目中排序后的结果显示，两个 16 的相对位置保持不变（$16$ 在 $16*$ 前面），说明该算法是**稳定**的。 A. 冒泡（稳定） B. 快速（不稳定） C. 归并（稳定） D. 插入（稳定）所以不可能是快速排序。

数据结构期末速通

数据结构期末考前救急

1 模式匹配

1.1 核心解题步骤

2 二叉树构建与线索化

2.1 基于遍历序列构建二叉树

2.1.1 中序+后序遍历构建

2.1.2 前序+中序遍历构建

2.2 中序线索二叉树

3 树的节点个数计算（以度为3的树为例）

3.1 核心公式

3.2 例题

4. 二叉排序树 (BST) 复习笔记

4.1 构建规则

4.2 例题：构建与查找分析

1. 构建过程图解

2. 查找次数计算

3. 平均查找长度 (ASL) 计算

4.3 节点的删除操作

5 广义表

5.1 核心概念计算

5.2 存储结构画法

6 数组存储地址计算

6.1 核心公式

6.2 例题

7 二叉树相关代码设计

7.1 求二叉树节点总数

7.2 求二叉树高度

7.3 输出二叉树叶子节点

8 哈弗曼树与编码

8.1 哈弗曼树构建规则

8.2 例题：构建与编码

8.3 带权路径长度 (WPL)

9 最小生成树

9.1 Prim算法（从节点出发）

9.2 Kruskal算法（从边出发）

10 图的遍历

10.1 深度优先遍历（DFS）

10.2 广度优先遍历（BFS）

一、 线性探测法 (Linear Probing)

1. 原理

2. 核心考点：堆积（Clustering）现象

3. 示例简述

二、 二次探测法 (Quadratic Probing)

1. 原理

2. 举例演示（必看）

3. 优缺点

三、 链地址法 (Chain Address / 拉链法)

1. 原理

2. 结构图示

3. 链地址法的 ASL 计算（与开放定址法完全不同！）

4. 优缺点（高频考点）

四、 三种方法的终极对比（考前背诵）

12 排序 (Sorting)

12.1 基本概念

12.2 插入排序 (Insertion Sort)

1. 直接插入排序 (Direct Insertion Sort)

2. 希尔排序 (Shell Sort)

12.3 交换排序 (Exchange Sort)

1. 冒泡排序 (Bubble Sort)

2. 快速排序 (Quick Sort) —— ★ 重中之重

12.4 选择排序 (Selection Sort)

1. 简单选择排序 (Simple Selection Sort)

2. 堆排序 (Heap Sort) —— 难点

12.5 归并排序 (Merge Sort)

12.6 核心对比表（★背诵★）

12.7 考试解题方法论

题型一：手写排序过程

题型二：排序算法的选择

题型三：复杂度与稳定性判断

模拟练习

woodfish

一、线性探测法 (Linear Probing)

二、二次探测法 (Quadratic Probing)

三、链地址法 (Chain Address / 拉链法)

四、三种方法的终极对比（考前背诵）