数据结构与算法详细复习笔记

第2章：线性表 (Linear List)

1. 基本概念

• 定义：由 $n(n\ge 0)$ 个数据特性相同的元素构成的有限序列。
  • 特性：
    • 有序性：元素之间有逻辑上的顺序（第一个、最后一个、前驱、后继）。
    • 有限性：元素个数有限。
• 抽象数据类型 (ADT)：
  • 数据对象：$D=\{a_i|a_i\in ElemSet,i=1,2,...,n\}$
  • 数据关系：$R=\{<a_{i-1},a_i>|a_{i-1},a_i\in D,i=2,...,n\}$
  • 基本操作：InitList, DestroyList, ListInsert, ListDelete, GetElem, LocateElem 等。

2. 顺序表 (Sequential List)

• 定义：用一组地址连续的存储单元依次存储线性表的数据元素。
• 特点：
  • 随机存取：通过首地址和下标可在 $O(1)$ 时间内访问任意元素。公式：$Loc(a_i)=Loc(a_1)+(i-1)\times L$。
  • 存储密度高：无需为逻辑关系（指针）额外分配空间。
  • 缺点：插入/删除需要移动大量元素（平均移动 $n/2$），需预分配空间（静态分配易溢出，动态分配需扩容）。

3. 链表 (Linked List)

• 单链表 (Singly Linked List)：
  • 结构：结点 = 数据域 (data) + 指针域 (next)。
  • 头结点：在首元结点前附设的一个结点，便于处理空表和统一插入/删除操作。
  • 建立方法：
    • 头插法：新结点插入头结点之后，读入顺序与链表顺序相反（逆序）。
    • 尾插法：维护一个尾指针 r，新结点插在 r 之后，读入顺序与链表顺序相同。
• 双向链表 (Doubly Linked List)：
  • 结构：结点包含 prior (前驱) 和 next (后继) 指针。
  • 插入操作 (s 插在 p 之后)：
    1. s->prior = p;
    2. s->next = p->next;
    3. p->next->prior = s;
    4. p->next = s; (注意顺序，防止断链)
  • 删除操作 (删除 p 的后继节点 q)：
    1. p->next = q->next;
    2. q->next->prior = p;
    3. free(q);
• 循环链表 (Circular Linked List)：
  • 特点：表中最后一个结点的指针指向头结点，形成环状。
  • 判空/遍历结束：指针是否等于头指针 (or 尾指针)。
  • 优势：从任意结点出发均可遍历全表；若设尾指针 rear，则查找头尾的时间均为 $O(1)$（便于合并两个链表）。
• 静态链表：
  • 利用数组实现，元素包含 data 和 cur (游标，即下个元素的数组下标)。
  • 适用于不支持指针的语言（如 BASIC）或数据量固定且需频繁操作指针的场景。
• 块状链表 (Unrolled Linked List)：
  • 每个结点存储多个数据元素（即一个小的顺序表）。平衡了顺序表（空间紧凑）和链表（插入删除快）的优缺点。

4. 应用

• 一元多项式相加：利用链表按指数升序存储。遍历两个链表，比较指数大小：
  • 指数相同：系数相加，若非零则保留。
  • 指数不同：将指数小的项链入结果链表。
• 大整数处理：利用链表存储大整数的每一位（或每几位），便于进位处理。

---

第3章：栈与队列 (Stack & Queue)

1. 栈 (Stack)

• 定义：只允许在表尾（栈顶 Top）进行插入（Push）和删除（Pop）的线性表。LIFO (Last In First Out)。
• 实现：
  • 顺序栈：top 指针指向栈顶元素（或栈顶上一个空位）。需判断 StackOverflow (上溢) 和 StackUnderflow (下溢，即空栈 pop)。
  • 共享栈：两个栈共享一段空间，栈底在两端，栈顶向中间延伸，top1 + 1 == top2 时满。
• 应用：
  • 递归：系统栈保存每一层调用的局部变量、返回地址。
  • 括号匹配：左括号压栈，右括号弹栈匹配。
  • 表达式求值：
    • 中缀转后缀 (RPN)：遇操作数输出；遇运算符与栈顶比较优先级。
    • 后缀计算：遇操作数压栈；遇运算符弹栈计算结果并压栈。
  • 迷宫求解：DFS 深度优先搜索（回溯法）。

2. 队列 (Queue)

• 定义：只允许在表尾（Rear）插入，表头（Front）删除。FIFO (First In First Out)。
• 循环队列 (Circular Queue)：
  • 问题：顺序队列单纯 front++ rear++ 会导致“假溢出”（即前方有空位但 rear 已达上限）。
  • 解决：模运算。(rear + 1) % MAXSIZE。
  • 判空/判满：为了区分队空和队满，通常牺牲一个单元。
    • 队空：front == rear
    • 队满：(rear + 1) % MAXSIZE == front
    • 队长：(rear - front + MAXSIZE) % MAXSIZE
• 双端队列 (Deque)：两端均可入队、出队。
  • 变种：输入受限（一端入两端出）、输出受限（两端入一端出）。

---

第4章：字符串 (String)

1. 基本概念

• 串：零个或多个字符组成的有限序列。
• 子串：主串中任意连续字符组成的子序列。
• 存储：定长顺序存储（截断）、堆分配存储（动态指针）、块链存储。

2. 模式匹配算法

• 朴素模式匹配 (Brute-Force)：
  • 主串指针 i，模式串指针 j。
  • 失配时：i 回溯到 i - j + 1，j 回溯到 0。
  • 最坏时间复杂度：$O(n\times m)$。
• KMP 算法 (Knuth-Morris-Pratt)：
  • 核心：主串指针 i 不回溯，模式串指针 j 回退到 next[j]。
  • Next 数组：next[j] 表示模式串第 j 个字符前的子串中，最长相等前后缀的长度。
    • 当 S[i] != P[j] 时，j 移动到 next[j] 继续比较。
  • NextVal 数组（优化）：若 P[j] == P[next[j]]，则递归优化，避免重复无效比较。
  • 时间复杂度：$O(n+m)$。

---

第5章：数组和广义表

1. 数组

• 存储：内存是一维的，多维数组需映射。
  • 行优先 (Row-Major)：C/C++。LOC(a[i][j]) = LOC(0,0) + (i * n + j) * size。
  • 列优先 (Column-Major)：Fortran。

2. 矩阵压缩存储

• 对称矩阵：$a_{ij}=a_{ji}$。只存上三角或下三角。按行优先存储下三角元素 $(i\ge j)$ 的下标 $k=\frac{i(i+1)}{2}+j$。
• 稀疏矩阵 (Sparse Matrix)：
  • 三元组表：(i, j, value)。空间优化，但丧失随机存取特性。
  • 十字链表：每个非零元节点既在行链表上，又在列链表上。便于频繁插入删除。

3. 广义表 (Generalized List)

• 定义：$LS=(a_1,a_2,...,a_n)$，其中 $a_i$ 可以是原子或子表。
• 重要操作：
  • GetHead(L)：取表头（第一个元素，可能是原子或列表）。
  • GetTail(L)：取表尾（除第一个元素外剩余元素构成的表，结果一定是一个表）。
  • 例：$L=((a,b),c)$，Head(L)=$(a,b)$，Tail(L)=$(c)$。

---

第6章：树与二叉树

1. 二叉树 (Binary Tree)

• 性质：
  1. 第 $i$ 层至多 $2^{i-1}$ 个结点。
  2. 深度为 $k$ 至多 $2^k-1$ 个结点。
  3. 核心性质：$n_0=n_2+1$（叶子结点数 = 度为2的结点数 + 1）。
• 完全二叉树 (Complete Binary Tree)：
  • 编号规则与满二叉树一一对应。
  • 数组存储时，结点 $i$ 的左孩子为 $2i$，右孩子为 $2i+1$，父节点 $\lfloor i/2\rfloor$。

2. 遍历 (Traversal)

• 前序 (Pre)：根 -> 左 -> 右
• 中序 (In)：左 -> 根 -> 右
• 后序 (Post)：左 -> 右 -> 根
• 层序：利用队列实现 BFS。
• 构造：
  • 前序 + 中序 -> 唯一确定二叉树。
  • 后序 + 中序 -> 唯一确定二叉树。
  • 前序 + 后序 -> 不能唯一确定（无法区分左右子树）。

3. 应用

• 哈夫曼树 (Huffman Tree)：
  • 构造：每次选取权值最小的两棵树合并，新树权值为两者之和，直到只剩一棵。
  • WPL (带权路径长度)：$\sum (\mathrm{叶}\mathrm{子}\mathrm{权}\mathrm{值}\times \mathrm{路}\mathrm{径}\mathrm{长}\mathrm{度})$。
  • 哈夫曼编码：前缀编码（任一字符编码都不是另一字符编码的前缀），用于数据压缩。
• 线索二叉树：
  • 利用空闲指针域（lchild若空指向前驱，rchild若空指向后继），通过 ltag/rtag 标记。
  • 加快遍历速度，无需递归或栈。

---

第7章：图 (Graph)

1. 存储结构

• 邻接矩阵：AdjMatrix[i][j] = 1 或权值。
  • 优点：易判断两点是否相连，易算度（行和列和）。
  • 缺点：稀疏图浪费空间 $O(n^2)$。
• 邻接表：顶点表 + 边表（链表）。
  • 优点：节省空间 $O(n+e)$。
  • 缺点：求入度麻烦（需遍历全表或使用逆邻接表）。

2. 遍历

• DFS (深度优先)：类似树的先序遍历，使用递归/栈。
• BFS (广度优先)：类似树的层序遍历，使用队列。最短路径特性（无权图）。

---

第8章：图的应用 (重难点)

1. 最小生成树 (MST)

• Prim 算法：
  • 思想：归并点。从一个顶点开始，每次选一条连接“已选集合”和“未选集合”且权值最小的边。
  • 复杂度：$O(n^2)$，适合稠密图。
• Kruskal 算法：
  • 思想：归并边。将边按权值排序，从小到大选边，若不构成回路（利用并查集判断）则加入。
  • 复杂度：$O(e\log e)$，适合稀疏图。

2. 最短路径

• Dijkstra 算法：
  • 单源最短路。贪心策略。每次从未标记节点中选距离源点最近的节点，松弛其邻接点。
  • 限制：边权不能为负。
  • 复杂度：$O(n^2)$。
• Floyd 算法：
  • 多源最短路。动态规划。A[i][j] = min(A[i][j], A[i][k] + A[k][j])。
  • 复杂度：$O(n^3)$。

3. AOV 网与拓扑排序

• 定义：顶点表示活动，边表示优先关系。
• 算法：
  1. 选择入度为 0 的顶点输出。
  2. 删除该顶点及其出边。
  3. 重复直到图空或无入度为 0 的点（说明有环）。

4. AOE 网与关键路径

• 定义：边表示活动，边权为持续时间，顶点表示事件。
• 关键路径：从源点到汇点的最长路径（决定工程最短工期）。
• 计算：
  • 事件最早发生时间 ve（从前向后取max）。
  • 事件最晚发生时间 vl（从后向前取min）。
  • 活动最早/最晚开始时间 e / l。
  • 若 e == l，则为关键活动。

---

第9章：查找 (Search)

1. 动态查找树

• 二叉排序树 (BST)：左 < 根 < 右。中序遍历有序。插入/删除/查找平均 $O(\log n)$，最坏 $O(n)$（退化为链表）。
• 平衡二叉树 (AVL)：
  • 任一节点左右子树高度差（平衡因子 BF）绝对值 $\le 1$。
  • 调整：
    • LL型：右旋（Right Rotation）。
    • RR型：左旋（Left Rotation）。
    • LR型：先左旋后右旋。
    • RL型：先右旋后左旋。

2. 散列 (Hashing)

• 散列函数：H(key)。除留余数法 H(key) = key % p （p 为不大于表长的最大质数）。
• 处理冲突：
  • 开放定址法：
    • 线性探测：di = 1, 2, 3... (易产生聚集/堆积现象)。
    • 二次探测：di = 1^2, -1^2, 2^2, -2^2...。
  • 链地址法：相同 Hash 值的元素存入同一链表。
• ASL (平均查找长度)：衡量效率指标，依赖于装填因子 $\alpha =\frac{\mathrm{填}\mathrm{入}\mathrm{元}\mathrm{素}\mathrm{个}\mathrm{数}}{\mathrm{表}\mathrm{长}}$。

---

第10章：排序 (Sorting)

1. 算法复杂度与稳定性对比

类别	排序算法	平均时间	最坏时间	空间	稳定性	备注
插入	直接插入	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	适合基本有序/n较小
	希尔排序	$O(n^{1.3})$	$O(n^2)$	$O(1)$	不稳定	增量 $d$ 逐渐减半
交换	冒泡排序	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	标志位优化
	快速排序	$O(n\log n)$	$O(n^2)$	$O(\log n)$	不稳定	内排序最快，枢轴选择关键
选择	简单选择	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定	移动次数少
	堆排序	$O(n\log n)$	$O(n\log n)$	$O(1)$	不稳定	适合 Top K 问题
归并	归并排序	$O(n\log n)$	$O(n\log n)$	$O(n)$	稳定	空间换时间，外排序基础
基数	基数排序	$O(d(n+r))$	$O(d(n+r))$	$O(r)$	稳定	无需比较，分配+收集

2. 核心算法说明

• 快速排序 (Quick Sort)：
  • Partition：选取枢轴（pivot），将小于 pivot 的放左边，大于的放右边。
  • 最坏情况：有序或逆序（退化为冒泡）。
• 堆排序 (Heap Sort)：
  • 建堆：从 $\lfloor n/2\rfloor$ 处开始向下调整 (Heapify)。
  • 排序：交换堆顶与末尾元素，堆大小减1，重新向下调整。
  • 升序排序使用大顶堆。
• 归并排序：
  • Divide (分)：将数组对半切分。
  • Conquer (治)：递归排序子数组。
  • Merge (合)：合并两个有序数组。

---

---

附录：数据结构小测涉及公式与重点总结

通过分析《小测1 答案》、《小测2 答案》及《小测3_题目答案》，以下是针对考试重点涉及的公式、推导及核心结论的详细总结。

1. 栈与队列 (Stack & Queue)

卡特兰数 (Catalan Number)

• 应用场景：$n$ 个不同元素进栈，可能的出栈序列总数。
• 公式：$$C_n=\frac{1}{n+1}{C}_{2n}^n=\frac{(2n)!}{(n+1)!n!}$$
• 小测案例 (小测1 第6题)：
  • $n=3$ 时，出栈序列数为 $C_3=\frac{C_6^3}{4}=\frac{20}{4}=5$ 种。

双端队列输出序列

• 排除法逻辑 (小测1 第8题)：
  • 对于输入受限或输出受限的双端队列，通常通过模拟和排除法来判断非法序列。
  • 核心技巧：结合栈的后进先出特性与队列的先进先出特性进行模拟。

---

2. 数组与矩阵 (Arrays & Matrices)

三对角矩阵压缩存储

• 定义：元素仅分布在主对角线及上下两条对角线上。
• 下标映射公式 (小测1 第10题)：
  • 题目特定映射关系：$A[1..n][1..n]$ 压缩至 $B[1..3n-2]$。
  • 给定公式推导结果：$k=2i+j-2$。
  • 案例验证：$A[66][65]$ 对应 $k=2\times 66+65-2=195$。
  • 注意：通用公式通常为 $k=2i+j-3$ 或类似，考试时需严格根据题目给定的数组下标起始点（如从0还是从1开始）及排列方式进行推导。

KMP 算法 Next 数组计算

• 推导逻辑 (小测1 第13题)：
  • 若 $S[j]==S[k]$ (其中 $k=next[j-1]$)，则 $next[j]=k+1$。
  • 若不等，则令 $k=next[k]$ 继续回溯比较。
  • 案例：$S{=}^{\prime }aaa{b}^{\prime }$
    • $j=1,S{=}^{\prime }{a}^{\prime },next[1]=0$ (固定)
    • $j=2,S{=}^{\prime }{a}^{\prime },S[1]==S[0]$? (前缀比较), $next[2]=1$
    • $j=3,S{=}^{\prime }{a}^{\prime },S[2]==S[1]\to next[3]=2$
    • $j=4,S{=}^{\prime }{b}^{\prime },S[3]\ne S[2]$, 回溯...

---

3. 树与二叉树 (Trees)

二叉树节点性质公式

1. 度数关系：

   • $$n_0=n_2+1\$\$(\mathrm{叶}\mathrm{子}\mathrm{结}\mathrm{点}\mathrm{数}=\mathrm{度}\mathrm{为}2\mathrm{的}\mathrm{结}\mathrm{点}\mathrm{数}+1)$$
     • 总节点数 $n=n_0+n_1+n_2$
     • 总分支数 $B=n-1=n_1+2n_2$
     • 联立消去 $n_1$，得 $n_0=n_2+1$。
   • 小测陷阱 (小测2 第1题)：已知总数 $n=98$，$n_1=48$，求叶子数。
     • $n_0+48+n_2=98\Rightarrow n_0+n_2=50$
     • 代入 $n_0=n_2+1\Rightarrow 2n_2+1=50\Rightarrow 2n_2=49$。
     • $n_2$ 必须为整数，故不存在这样的树。

2. 完全二叉树 (Complete Binary Tree)

   • 叶子结点数：$$n_0 = \lceil n/2 \rceil$$ (当 $n$ 为奇数时 $n_0=(n+1)/2$，偶数时 $n_0=n/2$)。
   • 案例 (小测2 第3题)：$n=47$ (奇数)，$n_0=(47+1)/2=24$。

3. 哈夫曼树 (Huffman Tree)

   • 特性：只有度为0和度为2的结点，不存在度为1的结点 ($n_1=0$)。
   • 节点总数公式：$$n=2n_0-1$$
   • 推导：$n=n_0+n_2$，且 $n_2=n_0-1\Rightarrow n=n_0+(n_0-1)=2n_0-1$。
   • 小测结论 (小测2 第12题)：若有 $n$ 个叶子结点（题目用 $n$ 表示 $n_0$），则总结点数为 $2n-1$。

4. 森林与树的转换

   • 连通分量/树的数量计算 (小测2 第9题)：
     • 若森林有 $N$ 个结点，$K$ 条边，则森林中树的棵数 $T$ 为：$$T=N-K$$
     • 推导：每棵树 (连通分量) 的边数 = 节点数 - 1。设第 $i$ 棵树有 $v_i$ 个节点，则边数 $e_i=v_i-1$。
     • 总边数 $K=\sum (v_i-1)=\sum v_i-\sum 1=N-T\Rightarrow T=N-K$。

---

4. 图 (Graphs)

握手定理 (Handshaking Lemma)

• 公式：所有顶点的度数之和等于边数的2倍。$$\sum _{v\in V}\mathrm{deg}(v)=2|E|$$
• 最少顶点数求解 (小测3 第2题)：
  • 已知：$|E|=16$ (度数和32)。
  • 已知点：3个度4，4个度3。已知度数和 $3\times 4+4\times 3=24$。
  • 剩余度数：$32-24=8$。
  • 约束：其余顶点度数 $<3$ (即最大为2)。
  • 目标：顶点数最少 $\to$ 剩余顶点度数尽可能大 $\to$ 设其余点度数均为2。
  • 剩余点数：$8/2=4$ 个。
  • 总顶点数：$3+4+4=11$ 个。

最小生成树 (MST)

• 唯一性判定 (小测3 第8题)：
  • 当无向连通图的最小生成树不唯一时，Prim 和 Kruskal 算法生成的结果可能不同。
  • 当最小生成树唯一时，两者结果必然相同。

关键路径 (Critical Path)

• 计算方法 (小测3 第11题)：
  • 路径长度 = 路径上所有活动（边）持续时间之和。
  • 关键路径 = 源点到汇点的最长路径。
  • 案例：路径 $V_0\to V_1\to V_4\to V_6\to V_8$。
  • 长度计算：$6+1+9+2=18$。

排序算法深度解析 (Sorting Algorithms Deep Dive)

本文档对常见的排序算法进行展开讲解，包含核心思想、算法步骤、过程演示、复杂度分析及代码逻辑。

---

1. 插入排序类 (Insertion Sorts)

1.1 直接插入排序 (Direct Insertion Sort)

核心思想： 将数组分为“已排序区间”和“未排序区间”。每次从未排序区间取出一个元素，在已排序区间中从后向前扫描，找到合适位置插入。类似于抓扑克牌的过程。

算法步骤：

1. 默认第 1 个元素已排序。
2. 取出第 2 个元素 temp，与第 1 个比较。若 temp < arr[1]，则 arr[1] 后移，temp 插入开头。
3. 重复直到所有元素归位。

过程演示 (排序 [5, 2, 4, 6, 1, 3])：

• 初始：[5] | 2, 4, 6, 1, 3
• 取 2：2 比 5 小，5 后移。 -> [2, 5] | 4, 6, 1, 3
• 取 4：4 比 5 小，5 后移；4 比 2 大，停。 -> [2, 4, 5] | 6, 1, 3
• ...以此类推。

核心代码逻辑 (C/C++)：

void InsertSort(int A[], int n) {
    int i, j, temp;
    for (i = 1; i < n; i++) {       // 从第2个元素开始
        if (A[i] < A[i-1]) {        // 若小于前驱，需插入
            temp = A[i];            // 暂存当前元素
            for (j = i-1; j >= 0 && A[j] > temp; --j) {
                A[j+1] = A[j];      // 大于temp的元素后移
            }
            A[j+1] = temp;          // 插入
        }
    }
}

分析：

• 最好情况：$O(n)$（已是有序，只需比较不移动）。
• 最坏情况：$O(n^2)$（逆序）。
• 稳定性：稳定（因为 A[j] > temp 才移动，相等时不移动）。

---

1.2 希尔排序 (Shell Sort)

核心思想： 又称“缩小增量排序”。是直接插入排序的优化版。通过将数组按增量 d 分组，对每组进行直接插入排序，使数组“基本有序”，最后 d=1 时再进行一次直接插入。

为什么比直接插入快？ 直接插入在基本有序时效率极高。希尔排序前期移动步长长，能快速消除逆序对；后期步长短但数组已基本有序，移动次数少。

过程演示： 数组 [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]，$n=10$。

1. d=5 (分5组: 8,3, 9,5, 1,4, 7,6, 2,0)：
   • 组内排序后 -> [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
2. d=2 (分2组: 3,1,0,9,7, 5,6,8,4,2)：
   • 组内排序后 -> [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
3. d=1 (整体直接插入)：
   • 微调 -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

分析：

• 复杂度：依赖于增量序列，平均约 $O(n^{1.3})$。
• 稳定性：不稳定（相同元素可能分在不同组，跳跃式移动导致相对位置改变）。

---

2. 交换排序类 (Exchange Sorts)

2.1 冒泡排序 (Bubble Sort)

核心思想： 两两比较相邻记录，如果反序则交换，直到没有反序的记录为止。每趟遍历将最大的元素“浮”到最后（或最小的“沉”到最前）。

优化点： 设置 flag 变量。若某一趟遍历中没有发生任何交换，说明已经有序，直接结束算法。

分析：

• 最好情况：$O(n)$（有序，第一趟 flag 未变直接退出）。
• 最坏情况：$O(n^2)$。
• 稳定性：稳定。

---

2.2 快速排序 (Quick Sort) —— 最重要的排序算法

核心思想： 分治法 (Divide and Conquer)。

1. 选基准 (Pivot)：通常选第一个元素。
2. 划分 (Partition)：将比基准小的移到左边，比基准大的移到右边。基准归位。
3. 递归：对左右两个子序列重复上述过程。

Partition 过程详解 (双指针法)： 设基准 pivot = A[low]，low 指向首，high 指向尾。

1. High 向左找小：while (low < high && A[high] >= pivot) high--; 找到比 pivot 小的，移到 low 处 (A[low] = A[high])。
2. Low 向右找大：while (low < high && A[low] <= pivot) low++; 找到比 pivot 大的，移到 high 处 (A[high] = A[low])。
3. 重复直到 low == high，将 pivot 放入 A[low]。

代码片段：

int Partition(int A[], int low, int high) {
    int pivot = A[low]; // 选第一个为基准
    while (low < high) {
        while (low < high && A[high] >= pivot) high--;
        A[low] = A[high];
        while (low < high && A[low] <= pivot) low++;
        A[high] = A[low];
    }
    A[low] = pivot;
    return low; // 返回基准位置
}

分析：

• 平均复杂度：$O(n\log n)$。
• 最坏复杂度：$O(n^2)$。发生在有序或逆序时，基准每次都选到最大/最小，退化为冒泡。
• 空间复杂度：$O(\log n)$ (递归栈的高度)。
• 稳定性：不稳定（Partition 过程中的远距离交换）。

---

3. 选择排序类 (Selection Sorts)

3.1 简单选择排序 (Simple Selection Sort)

核心思想： 第 $i$ 趟从 $A[i...n]$ 中选出最小的元素，与 $A[i]$ 交换。

特点：

• 交换次数少：最多 $n-1$ 次（优于冒泡）。
• 比较次数多：固定 $\frac{n(n-1)}{2}$ 次。
• 稳定性：不稳定。
  • 例子：[5, 8, 5, 2, 9]。第一趟，第一个 5 会和 2 交换，跑到第二个 5 后面。

---

3.2 堆排序 (Heap Sort)

核心思想： 利用堆（完全二叉树）这种数据结构。

• 大顶堆：$A[i]\ge A[2i+1]$ 且 $A[i]\ge A[2i+2]$。用于升序排序。
• 小顶堆：用于降序排序。

算法步骤：

1. 建堆：将无序数组构造成一个大顶堆。
   • 从最后一个非叶子结点 ($\lfloor n/2\rfloor -1$) 开始，从右至左，从下至上进行“下沉”调整 (HeapAdjust / sift_down)。
2. 排序：
   • 将堆顶元素（最大值）与堆底末尾元素交换。
   • 将剩余 $n-1$ 个元素重新调整为大顶堆。
   • 重复直至堆大小为 1。

下沉 (sift_down) 逻辑： 判断节点 k，其左孩子 2k+1，右孩子 2k+2。 若孩子比父节点大，则将最大的孩子与父节点交换，并继续向下追踪被交换的孩子节点。

分析：

• 复杂度：$O(n\log n)$。建堆 $O(n)$，调整 $O(n\log n)$。
• 优势：在 Top K 问题（选出前 K 大）中表现极佳。
• 稳定性：不稳定。

---

4. 归并排序 (Merge Sort)

核心思想： 分治法。

1. 分：将数组从中间切开，递归切分，直到长度为 1。
2. 治 (Merge)：将两个有序的子数组合并成一个有序数组。

Merge 过程： 需申请一个辅助数组 B[]。 比较左半区 A[i] 和右半区 A[j]：

• 若 A[i] <= A[j]，将 A[i] 放入 B，i++。
• 若 A[i] > A[j]，将 A[j] 放入 B，j++。
• 最后将剩余元素复制进 B，再把 B 拷回 A。

分析：

• 复杂度：$O(n\log n)$。
• 空间复杂度：$O(n)$（需要辅助数组，这是它最大的缺点）。
• 稳定性：稳定（Merge 时 A[i] <= A[j] 优先取左边，保证相对位置不变）。

---

5. 基数排序 (Radix Sort)

核心思想： 不基于比较的排序。利用“分配”和“收集”。 通常针对非负整数。将整数按位数切割成不同的数字，按每个位数分别比较。

步骤 (LSD - Least Significant Digit)：

1. 按个位排序：准备 10 个桶 (0-9)。遍历数组，按个位数字放入对应桶。按顺序收集回来。
2. 按十位排序：基于上一步结果，按十位放入桶，再收集。
3. ...直至最高位。

分析：

• 复杂度：$O(d(n+r))$。
  • $d$：最大数字的位数（决定遍历几趟）。
  • $n$：元素个数。
  • $r$：基数（如十进制 r=10，决定桶的个数）。
• 稳定性：稳定（必须稳定，否则高位排序会打乱低位的顺序）。

---

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)$	稳定	交换、flag优化
快速	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	$O(\log n)$	不稳定	Partition、分治
简单选择	$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)$	不稳定	建堆、下沉
归并	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	稳定	合并、空间换时间