数据结构
本文系统梳理了研究生招生考试《计算机学科基础》科目中的数据结构部分的核心知识点。首先介绍了线性表的顺序表示和链式表示，比较了它们在插入和删除操作上的时间复杂度。接着，详细讨论了栈和队列的概念、存储结构及其应用，包括中缀表达式转后缀表达式的调度场算法。随后，文章介绍了数组的特殊矩阵压缩方法和稀疏矩阵的存储方式。
在树的部分，文章讲解了二叉树的遍历方法、线索二叉树、多叉树的转换与遍历、霍夫曼树的构造与编码，以及并查集的实现与路径压缩技术。图的部分涵盖了图的基本概念、存储结构、遍历算法、最短路径算法、最小生成树算法、拓扑排序和关键路径方法。
最后，文章深入探讨了各种排序算法，包括插入排序、冒泡排序、快速排序、选择排序、堆排序、归并排序、基数排序和计数排序，分析了它们的时间复杂度、空间复杂度和稳定性。通过本文的学习，读者可以全面掌握数据结构的基本理论和应用技巧，为研究生招生考试奠定坚实的基础。
（摘要由 OpenAI GPT 4o 生成）
第二章 线性表¶
线性表的顺序表示¶
顺序表 = 数组
线性表的链式表示¶
对比顺序表的优势：插入和删除元素是 \(\Omicron(1)\) 的时间复杂度，而顺序表是 \(\Omicron(n)\) 的时间复杂度；扩展空间便利。
(1) 单链表、双链表、循环链表的增删改查操作
(2) 链表中有无头节点对操作的影响
(3) 复杂度分析：找到关键节点（即，被操作的节点）的时间消耗
(4) 静态链表：用数组实现链表。实例：操作系统中磁盘空间管理的空闲链表法、文件物理结构分配中的显式和隐式链接分配。
第三章 栈和队列¶
栈¶
(1) 问可能的出栈序列的组合
a. \(n\) 个不同元素进栈，出栈序列的个数是卡特兰数 \(\displaystyle \frac{C_{2n}^{n}}{n+1}\)。（\(n\) 个不同元素可以构成的 BST 的个数也是卡特兰数）
b. 元素 \(X_1, \dots, X_n\) 顺序进栈，若元素 \(X_i\) 已经出栈，那么 \(X_i\) 之前的未出栈元素，在出栈序列中必然逆序排列。
(2) 栈的存储结构：顺序栈、链栈、共享栈
(3) 栈的应用：中缀转后缀（调度场算法）、后缀表达式求值、...
调度场算法：
对中缀表达式的每一个元素 X 按顺序检查，如果 X 是：
a. 操作数：直接添加到输出序列中
b. 运算符：比较 X 与运算符栈中栈顶元素的优先级，如果 X 的优先级高于栈顶元素，直接入栈；否则，将栈顶元素出栈，直到 X 的优先级高于栈顶元素，然后 X 入栈
c. 左括号：直接入栈
d. 右括号：将栈顶元素出栈，直到遇到左括号，左括号出栈，丢弃这一对括号
直到输入队列为空，将栈中剩余元素依次出栈，即得到后缀表达式。
队列¶
(1) 顺序存储的队列：循环队列的满判断？
牺牲一个存储位置的方法：插入位置 (rear + 1) % N，删除位置 (front + 1) % N，队列满的条件画图判断即可
(2) 链式存储的队列：含头节点、头尾指针的单链表
(3) 双端队列问组合：双端队列两端不一定都支持插入和删除操作。输入受限的双端队列 = 只有一个端口支持插入操作，两个端口都支持删除操作。输出受限的双端队列 = 只有一个端口支持删除操作，两个端口都支持插入操作。
a. 实际上是栈 + 队列的组合，通过画图、分割解决问题
b. 已知输入队列为 1, 2, 3, 4，问能由输入受限的双端队列得到的输出序列个数、能由输出受限的双端队列得到的输出序列个数、既不能由输入受限的双端队列，也不能由输出受限的双端队列得到的输出序列（4, 2, 3, 1） 画图穷举，部分情况可以归约为栈的问题（用卡特兰数验证）
数组¶
(1) 特殊矩阵的压缩
a. 对称矩阵：只存储上三角或下三角，问第 \(i\) 行 \(j\) 列元素的存储位置
b. 上下三角矩阵：只存储上三角或下三角，问第 \(i\) 行 \(j\) 列元素的存储位置
c. 三对角矩阵：只存储有值的元素，本质是建立二维坐标和一维坐标的映射关系
d. 稀疏矩阵：用三元组存储 [i, j, value]，不支持随机访问（必须要遍历每一个三元组，对比 i 和 j）
(2) 稀疏矩阵的压缩
第四章 串¶
KMP 算法¶
匹配串 S 和模式串 T，在匹配失败时，利用已经匹配的信息（部分匹配值），尽量减少回溯的位。
规定下标从 1 开始。假设 T = "ababc"。
(1) 计算模式串 T 的部分匹配值，子串的部分匹配值等于前缀和后缀集合的交集中最长元素的长度
T[1:1] = "a"，其前缀和后缀都为空集，部分匹配值为 0
T[1:2] = "ab"，其前缀为 ["a"]，后缀为 ["b"]，部分匹配值为 0
T[1:3] = "aba"，其前缀为 ["a", "ab"]，后缀为 ["ba", "a"]，部分匹配值为 1
T[1:4] = "abab"，其前缀为 ["a", "ab", "aba"]，后缀为 ["bab", "ab", "b"]，部分匹配值为 2
T[1:5] = "ababc"，其前缀为 ["a", "ab", "aba", "abab"]，后缀为 ["babc", "abc", "bc", "c"]，部分匹配值为 0
从而 T 的部分匹配值为 [0, 0, 1, 2, 0]
(2) 由部分匹配值构造 next 数组，next[j] = PM[j - 1] + 1（如果下标从 0 开始，则为 +0），next[1] = 0
这里，j 表示模式串 T 中的下标，j - 1 表示成功匹配的最后一个字符的下标。
(3) 匹配时，如果 T[j] != S[i]，则 j = next[j]，否则 j++，i++
(4) 优化：如果 T[next[j]] == T[j]，则 next[j] = next[next[j]]，直至 T[next[j]] != T[j] 或 next[j] = 0，因为回退到相同的字符，不能改变不匹配的情况，这样会做无意义的比较。
第五章 树¶
(1) 度为 2 的树和二叉树的区别：二叉树强调左右儿子
(2) 计算节点数问题
a. 假设度为 \(i\) 的节点有 \(n_i\) 个，总节点数为 \(\displaystyle N = \sum_{i} i \cdot n_i + 1\)（数儿子）
b. 设总边数为 \(E\)，总节点数为 \(N\)，则 \(N = E - 1\)（数头顶）
c. 完全二叉树的代数性质 \(\displaystyle \begin{cases} 2 n_2 + n_1 + 1 = N \\ n_2 + n_1 + n_0 = N \\ n_1 \in \{1, 0\} \end{cases}\)，前两条性质所有的二叉树都满足，可以推出 \(n_2 = n_0 + 1\)
二叉树的遍历¶
先序遍历、中序遍历、后序遍历、层序遍历
(1) 先序遍历：访问节点时就输出，然后递归访问左子树，再访问右子树
(2) 中序遍历：当节点的左子树被访问完成后，输出节点，再访问右子树
(3) 后序遍历：当节点的左右子树都被访问完成后，输出节点
(4) 层序遍历：逐层访问，从上到下，从左到右
(5) 从遍历结果恢复原先的二叉树：要求必须是 中序 + 任一。方法是：用另外一个遍历序列中的树根信息，分割中序遍历序列，根据任意子树遍历结果长度一致，分割另外一个遍历序列，即可递归构建二叉树。
线索二叉树¶
利用空的指针域（左 = pred，右 = succ）存储前驱和后继节点的信息，可以实现中序遍历的非递归算法。
若某个节点的在遍历结果中的 pred 或者 succ 无意义，那么置空。
多叉树¶
(1) 将多叉树转化为对应二叉树（左儿子右兄弟表示法）
(2) 多叉树的遍历
a. 先根遍历 \(\rightleftarrows\) 对应二叉树的先序遍历（遍历结果也是一致的）
b. 后根遍历 \(\rightleftarrows\) 对应二叉树的中序遍历
(3) 多叉树和对应二叉树的节点对应关系：每一个非叶节点都能够对应一个「无下一兄弟」的节点（它的最小儿子）
霍夫曼树和霍夫曼编码¶
WPL 最小的二叉树
(1) 构造：贪心算法，每次都结合权值和最小的两个子树成为一个新的树，从所有子树都是单个节点开始，直到只有一颗树。
(2) 结构性质：不存在度为 1 的节点，节点数 \(N = n + (n - 1)\)，其中 \(n\) 为元素个数
并查集¶
(1) 构造：Union() 合并两个子树；Find() 查找根节点，通过判断两个节点的根节点是否相同，来判断是否在同一个集合中。
(2) 结构：森林
(3) 表示：双亲表示法，子节点指向父节点。使用数组存储，根节点的元素值存储树的规模（负数），非根节点的元素值存储父节点的下标。
(4) 并查集的路径压缩：在查找根节点的过程中，将路径上的所有节点直接指向根节点
第六章 图¶
基本概念¶
(1) 无向图、有向图
(2) 连通图（无向图中，任意两个节点之间都有路径）、强连通图（有向图中，任意两个节点之间都有路径）
(3) 连通分量（无向图中的极大连通子图）、强连通分量（有向图中的极大强连通子图）
(4) \(n\) 个顶点的无向图，如果有 \(\geq n\) 条边，图中必有环
(5) 不连通的无向图，至多有 \(\displaystyle \frac{(n-1)(n-2)}{2}\) 条边
(6) 不连通的有向图，至多有 \((n-1)(n-2) + 1\) 条边
(7) 已知度为 \(i\) 的顶点数 \(n_i\)，边数 \(E\)，求顶点数 \(N\)
(8) 无向图中，边和度的关系：每条边产生两个度
(9) 有向图中，边和度的关系：每条边产生一个入度和一个出度
图的存储¶
矩阵、邻接表、十字表（有向图）、多重表（无向图）：避免重复存储边
图的遍历¶
(1) BFS：层序遍历，使用 visited[] 数组避免重复遍历，使用队列存储当前节点的未被访问的邻接节点
(2) DFS：先序遍历，使用 visited[] 数组避免重复遍历，对未被访问的节点递归使用 DFS
最短路径算法¶
(1) Dijkstra 算法：贪心算法，每次选择距离最近的节点，更新距离，单源最短路径，不支援含负权边的图，OSPF 路由算法
(2) Foyd 算法：动态规划，逐个节点作为中间节点，更新距离，直至收敛，全图最短路路径，支援含负权边的图，RIP 路由算法
(3) BFS：无权图的最短路径，层序遍历
最小生成树算法¶
(1) Prim 算法：用顶点生成最小生成树，每次选择与已有最小生成树连接的边权最小的边，并将对应的节点加入到最小生成树中。
时间复杂度与边数无关，适用于稠密图
(2) Kruskal 算法：贪心算法，对边按权排序，每次选择不成环的、最小边权的边。
时间复杂度与顶点数无关，适用于稀疏图
用有向无环图描述表达式¶
用二叉树描述表达式：父节点是运算符，左右子节点是操作数
用有向无环图描述表达式：复用相同的运算成分
拓扑排序¶
(1) 算法 1：每次选择入度为 0 的节点并输出，删除该节点和与之相连的边，直至图为空
实现：使用数组存储所有节点的入度（使用邻接表时，初始化这一数据需要耗时 \(\Omicron(e)\)），将入度为 0 的节点加入栈（这一过程耗时 \(\Omicron(n)\)），每次从栈中取出一个节点，输出，遍历邻接表中它的邻接节点，在数组中将它们的入度减 1，如果减 1 后入度为 0，加入栈。节点状态更新的次数为 \(\Omicron(e)\)，更新时就可以将满足条件的元素加入栈，所以总的时间复杂度为 \(\Omicron(n + e)\)
(2) 算法 2：DFS
(3) 应用：用顶点描述活动的网络（AOV 网络）
关键路径¶
在用边描述活动的网络（AOE网络）中需求：算源点和汇点之间的最长路径、算事件（节点）发生的最早/最晚时间、算活动（边）的最早/最晚开始时间、算关键路径
(1) 算法：拓扑排序两次。
从源点开始，计算每个节点的最早开始时间（令源点的开始时间为 0）。
从汇点开始，计算每个节点的最晚开始时间（令汇点的开始时间为上面算出的汇点的最早开始时间）。
计算每个节点的最早开始时间和最晚开始时间的差值，该值为 0 的所有节点连接而成的路径即为关键路径。
(2) 缩短工程工期：不断减少关键路径上的活动时间（边的权值），每次缩短，重新计算关键路径。
第七章 查找¶
顺序查找（无序）、折半查找（有序）、分块查找（块内有序、块间无序）¶
(1) 顺序查找：时间复杂度 \(\Omicron(n)\)
(2) 折半查找：时间复杂度 \(\Omicron(\log n)\)
(3) 分块查找：时间复杂度 \(\Omicron(\sqrt{n})\)
(4) 画判定树：对于折半查找来说，是一颗平衡二叉树。画法：每一个子树，其根节点是 mid，左子树是比它小的元素，右子树是比它大的元素。
(5) 算 ASL：假设判定树上的每一个节点有相同的到达概率（包括虚构的失败节点）
(6) 分块查找如何分块：对 [a1, a2, a3, b1, b2, b3, c1, c2] 有 ai < bi，bi < ci，分块为 [a1, a2, a3], [b1, b2, b3], [c1, c2]，理想分块大小是 \(\sqrt{n}\)
BST¶
BST 中序遍历将直接得出排序结果。BST 维护偏序关系，左子树 < 根节点 < 右子树。
(1) 查找：从根节点逐层向下查找
(2) 插入：查找（如果插入的元素和树中已有的元素是不同的，那么查找必然失败），直到叶节点。插入新的节点，成为这个叶节点的左儿子或右儿子。
(3) 删除：有三种情况
a. 删除的节点没有左子树：直接使用右子树替代被删除的节点；
b. 删除的节点没有右子树：直接使用左子树替代被删除的节点；
c. 删除的节点有左右子树：找到左子树中最大的节点或右子树中最小的节点，替代被删除的节点。这个被用于替代的节点必然是 a 或 b 的情况。
AVL 树¶
左右子树的高度差不超过 1，在插入或删除时需要调整二叉树以满足这一性质。
(1) 插入：使用 BST 的插入方式插入，如果发生不平衡，从叶到根，调整不平衡的子树
(2) 删除：使用 BST 的删除方式删除，如果发生不平衡，从叶到根，调整不平衡的子树
(3) 调整不平衡的子树：可以归纳到四种情况：LL、LR、RR、RL。每一种旋转方式，旋转后得到的二叉树满足 AVL 性质，并且中序遍历结果不变。
(4) 深度为 \(h\) 的 AVL 树，最少节点数量满足 \(F(h) = F(h-1) + F(h-2) + 1\)，其中 \(F(0) = F(1) = 1\)，最多节点数量是满二叉树的情况。
RBT¶
(1) 红黑树是满足以下五条性质的 BST：
a. 每个节点要么是黑色的，要么是红色的；
b. 根节点是黑色的；
c. 叶节点是黑色的；
d. 每个叶节点，黑高相等；
e. 不存在两个相邻的红色节点。
为了方便起见，我们为每个有值的节点，使用黑色的 NIL 节点补充其缺失的子节点。
(2) 插入：
- 插入的节点是红色的；
- 判定插入节点的父节点：
- 如果插入节点的父节点是黑色的，OK；
- 如果插入节点的父节点是红色的，判定其叔节点：
- 红叔叔：反转父代、爷代的颜色
- 黑叔叔：将
n、n.p、n.p.p调整为高为 2 情况，重新染色使得这个子树根节点是黑色，子节点是红色。（黑叔叔意味着调整n、n.p、n.p.p不影响黑高）
- 如果调整后，整棵树的根节点是红色的，将根节点染黑；
- 上面的过程从叶到根，逐层向上调整。
(3) 删除：算了吧。
(4) 性质：
a. 从根到叶节点的最大长度不大于最小长度的两倍（红色节点不相连、最短为全黑）
b. 有 \(n\) 个节点的红黑树的高度不超过 \(2 \log(n + 1)\)（根的黑高至少为 \(\displaystyle \frac{h}{2}\)，最极端的情况：所有路径都是全黑的，此时总节点数 \(n \geq 2^{h/2} - 1\)）
B 树¶
\(m\) 阶 B 树，每一个非根节点中含有的元素数量 \(\in [\lceil m/2 \rceil - 1, m - 1]\)，即分叉数 \(\in [\lceil m/2 \rceil, m]\)。同时 B 树需要是平衡树。
(1) 查找：同 BST
(2) 插入：先查找到要插入的目标位置，如果节点元素 \(> m-1\)，分裂，以中间节点 \(\lceil m/2 \rceil\) 为界，左侧成为新的左侧节点，右侧成为新的右侧节点，中间元素进入父节点。分裂过程从叶到根，逐层向上调整。
(3) 删除：先查找到要从中删除的目标位置，如果节点元素 \(< \lceil m/2 \rceil - 1\)，则需要向兄弟节点借一个元素。如果够借，那么借一个节点过来，调整父节点的元素；如果不够借，兄弟节点合并，调整父节点中的元素。删除过程从叶到根，逐层向上调整。
(4) 优势：减少磁盘 I/O 次数，减少树的高度，提高查找效率。
B+ 树¶
只有叶节点存储数据，非叶节点只存储索引。
为了实现该目的，节点中每一个元素对应一个指向下一节点的指针，被指向的节点中，所有元素都小于等于该元素，大于等于该元素的前一个元素。
m 阶 B+ 树，每一个非根节点中含有的元素数量 \(\in [\lceil m/2 \rceil, m]\)，即分叉数 \(\in [\lceil m/2 \rceil, m]\)。同时 B+ 树需要是平衡树。
阶直接决定分叉数的范围，不论是 B 树还是 B+ 树。
无论查找成功与否，都需要遍历到叶节点。
散列表¶
(1) 哈希函数的确定
(2) 开放定址法，哈希碰撞的处理：
a. 线性探测：\(h(k, i) = (h'(k) + i) \mod m\)，\(i = 0, 1, 2, \dots\)，第一个空位插入
b. 平方探测：\(h(k, i) = (h'(k) + j) \mod m\)，\(j = 0, \pm 1^2, \pm 2^2, \dots\)，第一个空位插入，表长必须为 \(4k + 3\) 的一个素数
c. 双哈希：\(h(k, i) = (h_1(k) + i \cdot h_2(k)) \mod m\)，\(i = 0, 1, 2, \dots\)，第一个空位插入，\(h_2()\) 是另外一个哈希函数
开放定址法只能伪删除，否则会影响查找。
(3) 拉链法：每一个位置使用链表链接哈希值相同的元素
(4) 性能度量
a. 装填因子：\(\alpha = n/m\)，\(n\) 是元素个数，\(m\) 是表长
b. 平均查找长度：正向关于装填因子。
计算平均查找长度（成功）：计算每一个关键字的查找长度，然后求和
计算平均查找长度（失败）：考虑哈希函数的每一种可能结果中对应失败的查找所需要的查找长度，然后求和
第八章 排序¶
内部排序算法，注意要考察其最好、平均、最差复杂度，空间复杂度，稳定性。
插入排序¶
直接插入排序：每次排序，有序数列长度增加 1，直至全部有序。
(1) base case: 第一个元素本身就是有序的。
(2) inductive case: 将扫描到的一个元素插入到有序序列中，使得插入后的序列仍然有序。
| [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] |
|---|---|---|---|---|---|---|---|---|---|
| (29) | 11 | 45 | 14 | 8 | 37 | 22 | 3 | 50 | 19 |
| (11 | 29) | 45 | 14 | 8 | 37 | 22 | 3 | 50 | 19 |
| (11 | 29 | 45) | 14 | 8 | 37 | 22 | 3 | 50 | 19 |
| (11 | 14 | 29 | 45) | 8 | 37 | 22 | 3 | 50 | 19 |
| (8 | 11 | 14 | 29 | 45) | 37 | 22 | 3 | 50 | 19 |
| (8 | 11 | 14 | 29 | 37 | 45) | 22 | 3 | 50 | 19 |
| (8 | 11 | 14 | 22 | 29 | 37 | 45) | 3 | 50 | 19 |
| (3 | 8 | 11 | 14 | 22 | 29 | 37 | 45) | 50 | 19 |
| (3 | 8 | 11 | 14 | 22 | 29 | 37 | 45 | 50) | 19 |
| (3 | 8 | 11 | 14 | 19 | 22 | 29 | 37 | 45 | 50) |
(3) 如果规定遇到有序序列中，已有待插入的元素时，插入到有序序列中相同元素的后面，那么这个算法是稳定的。
(4) 最好情况：待排序序列已经有序，复杂度为 \(\Omicron(n)\)
(5) 最坏情况：待排序序列是逆序的，每一次插入需要与已经有序序列的所有元素进行比较，复杂度为 \(\Omicron(n^2)\)
(6) 平均情况：复杂度为 \(\Omicron(n^2)\)
(7) 空间复杂度：只使用了常数规模的辅助空间，\(\Omicron(1)\)
(8) 优化——折半插入排序：查找插入的位置时，使用二分查找，总的复杂度为 \(\Omicron(n\log n)\)
(9) 优化——希尔排序：分组，在每一组组内使用插入排序。减少分组大小，继续排序，直至分组大小为 1。
分组方法：下标同余分组规模 \(d\) 的元素分为一组。分组序列是一个递减的序列。根据所选取的递减序列，希尔排序的性能会有所不同。
希尔排序的优化原理：使得待排序的序列「更加有序」。
冒泡排序¶
一次排出一个极小元素，已排序部分必然是全局最小且有序的，未排序的部分可能会在一次排序操作中发送变化。
从后往前，两两比较相邻元素的值，将较小的元素向前移动。
一轮排序的过程：
| [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] |
|---|---|---|---|---|---|---|---|---|---|
| 29 | 11 | 45 | 14 | 8 | 37 | 22 | 3 | 50 | 19 |
| 29 | 11 | 45 | 14 | 8 | 37 | 22 | 3 | 19 | 50 |
| 29 | 11 | 45 | 14 | 8 | 37 | 22 | 3 | 19 | 50 |
| 29 | 11 | 45 | 14 | 8 | 37 | 3 | 22 | 19 | 50 |
| 29 | 11 | 45 | 14 | 8 | 3 | 37 | 22 | 19 | 50 |
| 29 | 11 | 45 | 14 | 3 | 8 | 37 | 22 | 19 | 50 |
| 29 | 11 | 45 | 3 | 14 | 8 | 37 | 22 | 19 | 50 |
| 29 | 11 | 3 | 45 | 14 | 8 | 37 | 22 | 19 | 50 |
| 29 | 3 | 11 | 45 | 14 | 8 | 37 | 22 | 19 | 50 |
| 3 | 29 | 11 | 45 | 14 | 8 | 37 | 22 | 19 | 50 |
完整的排序过程：
| [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] |
|---|---|---|---|---|---|---|---|---|---|
| 29 | 11 | 45 | 14 | 8 | 37 | 22 | 3 | 50 | 19 |
| (3) | 29 | 11 | 45 | 14 | 8 | 37 | 22 | 19 | 50 |
| (3 | 8) | 29 | 11 | 45 | 14 | 19 | 37 | 22 | 50 |
| (3 | 8 | 11) | 29 | 14 | 45 | 19 | 22 | 37 | 50 |
| (3 | 8 | 11 | 14) | 29 | 19 | 45 | 22 | 37 | 50 |
| (3 | 8 | 11 | 14 | 19) | 29 | 22 | 45 | 37 | 50 |
| (3 | 8 | 11 | 14 | 19 | 22) | 29 | 37 | 45 | 50 |
| (3 | 8 | 11 | 14 | 19 | 22 | 29) | 37 | 45 | 50 |
| (3 | 8 | 11 | 14 | 19 | 22 | 29 | 37) | 45 | 50 |
| (3 | 8 | 11 | 14 | 19 | 22 | 29 | 37 | 45) | 50 |
| (3 | 8 | 11 | 14 | 19 | 22 | 29 | 37 | 45 | 50) |
(1) 最好、平均、最差都是 \(\Omicron(n^2)\)
(2) 空间复杂度：只使用了常数规模的辅助空间，\(\Omicron(1)\)
(3) 如果规定两个元素相等时，不交换它们的位置，那么这个算法是稳定的。
快速排序¶
(1) 选择 pivot，划分待排序序列，使得 前 < pivot < 后。
(2) 方法：双工作指针交换：使用双指针从两个方向向中间扫描，并且可以保证其中一个指针总是记录了 pivot 的位置。
一轮排序的过程：
| [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | 备注 |
|---|---|---|---|---|---|---|---|---|---|---|
| 29 | 11 | 45 | 14 | 8 | 37 | 22 | 3 | 50 | 19 | pivot = 29 |
| p | 11 | 45 | 14 | 8 | 37 | 22 | 3 | 50 | 19 | i++ b-- |
| 19 | 11 | 45 | 14 | 8 | 37 | 22 | 3 | 50 | p | b 找到第一个小于 pivot 的元素，和 i 交换 |
| 19 | 11 | p | 14 | 8 | 37 | 22 | 3 | 50 | 45 | i 找到第一个大于 pivot 的元素，和 b 交换 |
| 19 | 11 | 3 | 14 | 8 | 37 | 22 | p | 50 | 45 | b 找到下一个小于 pivot 的元素，和 i 交换 |
| 19 | 11 | 3 | 14 | 8 | p | 22 | 37 | 50 | 45 | i 找到下一个大于 pivot 的元素，和 b 交换 |
| 19 | 11 | 3 | 14 | 8 | 22 | p | 37 | 50 | 45 | b 找到下一个小于 pivot 的元素，和 i 交换 |
| 19 | 11 | 3 | 14 | 8 | 22 | p | 37 | 50 | 45 | i == b 第一轮排序完成 |
| 19 | 11 | 3 | 14 | 8 | 22 | {29} | 37 | 50 | 45 |
完整的排序过程：在 前 < pivot < 后 的情况下，对两个子序列分别进行快速排序，直至子序列长度为 1，完成排序。
(1) 最好情况：每一次划分分出的两个子序列都是等长的，此时时间复杂度为 \(\Omicron(n\log n)\)
(2) 最坏情况：每一次划分分出的两个子序列都是一个长度为 \(0\) 和一个长度为 \(n-1\) 的极端情况，（基本有序、逆序）此时时间复杂度为 \(\Omicron(n^2)\)
(3) 平均情况：时间复杂度为 \(\Omicron(n\log n)\)
(4) 空间复杂度：递归调用的栈深度为 \(\Omicron(\log n)\)
(5) 稳定性：不稳定，考虑 [3, 2, 2] 的情况，pivot = 3，第一次交换位置将第二个 2 交换到第一个 2 的前面。
选择排序¶
每一轮排序，选择无序序列中的最小元素，与有序序列之后的第一个元素交换。
| [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] |
|---|---|---|---|---|---|---|---|---|---|
| 29 | 11 | 45 | 14 | 8 | 37 | 22 | 3 | 50 | 19 |
| (3) | 11 | 45 | 14 | 8 | 37 | 22 | 29 | 50 | 19 |
| (3 | 8) | 45 | 14 | 11 | 37 | 22 | 29 | 50 | 19 |
| (3 | 8 | 11) | 14 | 45 | 37 | 22 | 29 | 50 | 19 |
| (3 | 8 | 11 | 14) | 45 | 37 | 22 | 29 | 50 | 19 |
| (3 | 8 | 11 | 14 | 19) | 37 | 22 | 29 | 50 | 45 |
| (3 | 8 | 11 | 14 | 19 | 22) | 37 | 29 | 50 | 45 |
| (3 | 8 | 11 | 14 | 19 | 22 | 29) | 37 | 50 | 45 |
| (3 | 8 | 11 | 14 | 19 | 22 | 29 | 37) | 50 | 45 |
| (3 | 8 | 11 | 14 | 19 | 22 | 29 | 37 | 45) | 50 |
| (3 | 8 | 11 | 14 | 19 | 22 | 29 | 37 | 45 | 50) |
(1) 最好、平均、最差都是 \(\Omicron(n^2)\)
(2) 空间复杂度：只使用了常数规模的辅助空间，\(\Omicron(1)\)
(3) 稳定性：不稳定，考虑 [3, 3, 2] 的情况，第一次选择 2 交换和第一个 3 交换，导致两个 3 的相对位置发生变化。
堆排序¶
(1) 堆：一颗完全二叉树，树中每一个子树都满足：根节点的值小于等于子树中节点的值。（\(\Rightarrow\) 从根到叶的路径是有序的）
(2) 堆的插入：插到尾部，如果被插入的节点小于父节点，和父节点交换，迭代，直至被调整的节点大于其父节点，或已经调整到根节点。
(3) 堆的删除：删除根节点，将尾部元素放到根节点，如果根节点大于子节点，和子节点中较小的一个交换，迭代，直至被调整的节点小于其子节点，或已经调整到叶节点。
(4) 建堆——逐个插入建堆，\(\Omicron(n \log n)\)
(5) 建堆——原地建堆：找到最后一个有子节点的节点，使得其与其子节点满足堆序性（如果根节点大于子节点，和子节点中较小的一个交换，这可能会破坏子节点的堆序性，如果破坏，向下调整直至树根），然后调整前一个有子节点的节点，直至根节点。这个方法是 \(\Omicron(n)\) 的。
(6) 堆排序：建堆后，每次删除根节点，直至堆为空。
(7) 时间复杂度：\(\Omicron(n \log n)\)：建堆 \(\Omicron(n)\)，每次删除根节点 \(\Omicron(\log n)\)
(8) 空间复杂度：只使用了常数规模的辅助空间，\(\Omicron(1)\)
(9) 稳定性：不稳定，建堆时可能会破坏相同元素的相对位置。
归并排序¶
base case: 一个元素本身就是有序的。
inductive case: 将两个有序序列进行合并，可以使得合并后的序列有序。
(1) 时间复杂度：\(\Omicron(n \log n)\)：归并一次 \(\Omicron(n)\)，总共归并 \(O(\log n)\) 次数
(2) 空间复杂度：归并时需要一个辅助数组，\(\Omicron(n)\)
(3) 稳定性：稳定，合并时，如果两个元素相等，先取左边的元素
基数排序/桶排序¶
一次排对待排序序列中所有数字的一位进行排序。对 \(n\) 个 \(m\) 位 \(k\) 进制数进行排序，时间复杂度为 \(\Omicron(m(n+k))\)，此处，\(m\) 表示排序 \(m\) 轮，\(n\) 表示每一轮中的分配，\(k\) 表示每一轮中的收集。
(1) 分配：根据当前位的数字，将待排序的元素插入到对应的链表（桶）中，假设是十进制的情况，那么有 L[0], ..., L[9] 十个链表
(2) 收集：以 L[0], ..., L[9] 的顺序，将每个链表中的元素从链表头摘下，放到输出序列中
(3) 重复上面的过程，直至所有位都排完
(4) 稳定性：稳定，分配和收集的过程中，先分配的总是先收集
计数排序¶
利用地址空间帮助排序，把元素作为地址偏移量，将其出现的次数存在对应的地址空间中，然后统计等于每个元素的元素个数，根据这个信息生成输出序列。
由于破坏了附加信息，只保留数据本身，稳定性没有意义，或者认为是不稳定的。
外部排序¶
(1) 败者树：减少 \(k\) 路归并的比较次数至 \(\Omicron(n \log k)\)
败者树是为了归并排序时，输出所有有序子段中，最小的元素。记录败者的目的：让树中从根到叶的每一个节点，符合从小到大的顺序。
(2) 生成更大的初始归并段（置换-选择排序）
a. 目标：在工作区大小有限的情况下排成尽量长的有序段。
b. 方法：在工作区中，每次选择大于输出文件中最大元素的最小元素，输出到输出文件中。直至工作区中找不到符合此条件的元素。
例如：
| 输出文件 | 工作区(3) | 输入文件 |
|---|---|---|
| 11 45 23 19 30 42 27 17 | ||
| 11 45 14 | 23 19 30 42 27 17 | |
| 11 | 45 14 23 | 19 30 42 27 17 |
| 11 14 | 45 23 19 | 30 42 27 17 |
| 11 14 19 | 45 23 30 | 42 27 17 |
| 11 14 19 23 | 45 30 42 | 27 17 |
| 11 14 19 23 30 | 45 42 27 | 17 |
| 11 14 19 23 30 42 | 45 27 17 | |
| 11 14 19 23 30 42 45 # | 27 17 | |
| 27 17 | ||
| 17 | 27 | |
| 17 27 # |
(3) 减少归并的总 I/O 次数：问题转化为如何组织使用置换-选择排序生成的归并段。
对归并段按照其长度作为权值，组织为一个霍夫曼树，并且该树中只有度为 0 或 k 的节点，此时总读写次数最少，为 \(2 \cdot \text{WPL}\)。
虚段：为使得霍夫曼树中只有度为 0 或 k 的节点，有时需要额外添加的长度为 0 的虚段。
计算添加的虚段个数，根据以下的性质列方程：
a. 所有的归并段在构建霍夫曼树时，都会位于叶节点，即度为 0 的节点；
b. 对于只有度为 0 或 k 的节点的树，总节点数 \(N = n_k + n_0\)，其中 \(n_k\) 是度为 k 的节点数，\(n_0\) 是度为 0 的节点数；
c. 通过数儿子的方法，总节点数 \(N = k \cdot n_k + 1\)；
d. 联立上下两个方程，解得 \(\displaystyle n_k = \frac{n_0 - 1}{k - 1}\)；
e. 上面的方程需要在整数域中有解，因此 \(n_0 - 1\) 必须是 \(k - 1\) 的倍数；
f. 补充虚段，使得总归并段的数量满足 \(\equiv 1 \mod (k - 1)\)。