一、时间、空间复杂度

$O(1) < O(\log_2 n) < O(n) < O(n \log_2 n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$

• 加法规则：多项相加，保留最高阶项，并将系数化为 1。
• 乘法规则：都保留，并将系数化为 1
• 加法乘法混合规则：先小括号再乘法规则再加法规则

时间复杂度估算看最内层循环，如若没有循环和递归则为 O (1)。举个例子

def sum_of_numbers(n):
    result = 0
    for i in range(1, n+1):
        result += i
    return result

• 时间复杂度的计算方法：循环语句 for i in range (1, n+1) 会执行 n 次，所以时间复杂度为 O (n)。
• 空间复杂度的计算方法： 函数中只使用了一个整型变量 result，result 的存储占用不随输入 n 的大小而增加，所以空间复杂度为 O (1)，即常数级别。

所以，这个函数的时间复杂度为 O (n)，空间复杂度为 O (1)。

二、渐进符号

三、归式主观法时间、空间复杂度

递归算法的时间复杂度定义

• 每次递归时间复杂度不变：递归次数 * 每次递归的时间复杂度
• 如果每次递归的时间复杂度随着 n 变化而变化则要根据代码来观察

公式

$T(n) = aT\left(\frac{n}{b}\right) + f(n)$

其中，$a > 1$ 和 $b > 1$ 是常数，$f(n)$ 是一个渐进的正函数。

• 若对于某常数 $\varepsilon > 0$，有：$f(n) = O\left(n^{\log_b a - \varepsilon}\right)$，则：$T(n) = \Theta\left(n^{\log_b a}\right)$。

• 若：$f(n) = \Theta\left(n^{\log_b a} \log^k n\right)$，则：$T(n) = \Theta\left(n^{\log_b a} \log^{k+1} n\right)$。

• 若对于某常数 $\varepsilon > 0$，有：$f(n) = \Omega\left(n^{\log_b a + \varepsilon}\right)$，且对于某常数 $c < 1$ 与所有足够大的$n$ 有：$af\left(\frac{n}{b}\right) \leq cf(n)$，则：$T(n) = \Theta(f(n))$。

四、线性表

如果没有给出最好最坏平均时间复杂度的话就默认是平均时间复杂度

顺序表

采用顺序存储，实质是数组。通过索引（数组下标）访问元素，查询快，插入和删除慢。

优点	缺点
可以随机存取表中的元素	插入和删除需要移动大量的元素

时间复杂度

	插入、删除	查询
最好	O(1)	O(1)
平均	O(n)	O(1)
最坏	O(n)	O(1)

单链表

采用链式存储，实质是链表，每个节点包含数据域和指向下一个节点的指针。插入和删除快，查询慢。

优点	缺点
插入和删除不需要移动大量元素，只需要移动指针	不能随机访问表中的元素

时间复杂度

	插入、删除	查询
最好	O(1)	O(1)
平均	O(n)	O(n)
最坏	O(n)	O(n)

链表结构	普通单链表（ head ）	单向循环链表（ tail ）
在头部插入	O(1)	O(1)（ tail->next 就是头）
在尾部插入	O (n)（需遍历）	O(1)（直接改 tail ）
删除头部	O(1)	O(1)（ tail->next = tail->next->next ）
删除尾部	O (n)（需遍历）	O(n)（需找前驱）

总结

性能类别	具体项目	顺序存储	链式存储
空间性能	存储密度	(=1)，更优	(<1)
	容量分配	事先确定	动态改变，更优
时间性能	查找运算	O($\frac{n}{2}$)	O($\frac{n}{2}$)
	读运算	O (1)，更优	O($\frac{n+1}{2}$)，最好情况 (1)，最坏情况 (n)
	插入运算	O($\frac{n}{2}$)，最好情况为 (0)，最坏情况为 (n)	O (1)，更优
	删除运算	O($\frac{n-1}{2}$)	O (1)，更优

五、栈

栈是一种先进后出（后进先出）的线性结构，只能在栈的一端（栈顶）进行插入和删除。 递归使用栈

当两个栈共享储存空间时，栈满的条件是：栈 1 和栈 2 的栈顶相邻，也就是栈 1 顶 - 栈 2 顶 = 1

六、队列

队列是一种先进先出（First In, First Out，FIFO）的数据结构，其中最先进入队列的元素最先被移出。这类似于在排队时，先到达的人先离开队列。

队列通常有两个主要操作：

• 入队（enqueue），将元素添加到队尾；
• 出队（dequeue），从队头移除元素。

常见的题目有：

上图这种题目的解法，就是先把题目中的 M-1 或者 M-2 换成固定的值（按照顺序 M-1 就是 5）
所以就是 容量：6，长度：3，队尾：1，当这三个数代入四个选项，就能算出来

这种题基本上就是说 e1 e2 e3 e4 按照顺序进入，要么出队是 e1 e2 要么是 e2 e1 不可能出现 e3 e1 e1 e3 情况。

但是也仅仅局限于单出口，如果是双出口请根据答案具体分析。

七、栈与队列

用两个栈可以模拟队列操作，使用两个队列可以模拟栈的操作技术上可行，但实际应用中较少，且效率差异大。所以这句话存在问题：利用两个栈可以模拟一个队列的操作，反之亦可。

在做题的时候会遇到一些，先进入一个栈 / 队列，在进入一个队列 / 栈的问题，要记住是一个元素出来后就要立刻进入下一个了。

例如数组通过栈后立刻入队，那么出栈和出队的顺序一定相同。

八、串

字符串是线性结构，空格也是字符串

字串是指由主串中任意长度连续的字符构成的序列

例如：

• 主串：abc
• 字串：a、b、c、ab、bc
• ac 不是字串，因为它不是主串中连续的字符

九、串的匹配模式

朴素模式匹配

• 时间复杂度
  • 最好：O (m)
  • 最坏：O ($n \times m$)
  • 平均：O (n + m)
• 比较次数
  • 最好：m 次
  • 最坏：$(n - m + 1) \times m$
  • 平均：$\frac{1}{2}(n - m + 1)$

KMP 模式匹配

前缀是指不包含最后一个字符的子串。

后缀是指不包含第一个字符的子串。

next [k]= 前后缀中匹配的最长子串的长度 + 1。

例如：

• 对于字符串 "aab"
  • 前缀是： "a" , "aa"
  • 后缀是： "b" , "ab"
• next[i] 的值就是这些前缀和后缀中，最长相等部分的长度。

例题：求 aabbaa 的 next []，一般题中会给出特殊的 next[1] = 0 ， next[2] = 1 。 "aabbaa" 来一步步计算 next 数组。

初始化

• 模式串： "aabbaa"
• 长度：6
• 初始值： next[1] = 0 , next[2] = 1

计算过程

(1) 计算 next[3]

• 子串： "aab"
• 查找最长相同前后缀：
  • 前缀： "a" , "aa"
  • 后缀： "b" , "ab"
  • 比较发现，前缀和后缀没有相等的部分。
• 因此， next[3] = 0 + 1 = 1

(2) 计算 next[4]

• 子串： "aabb"
• 查找最长相同前后缀：
  • 前缀： "a" , "aa" , "aab"
  • 后缀： "b" , "bb" , "abb"
  • 比较发现，前缀和后缀没有相等的部分。
• 因此， next[4] = 0 + 1 = 1

(3) 计算 next[5]

• 子串： "aabba"
• 查找最长相同前后缀：
  • 前缀： "a" , "aa" , "aab" , "aabb"
  • 后缀： "a" , "ba" , "bba" , "abba"
  • 比较发现，前缀和后缀中只有第一个字符 "a" 相等。
• 因此， next[5] = 1 + 1 = 2

(4) 计算 next[6]

• 子串： "aabbaa"
• 查找最长相同前后缀：
  • 前缀： "a" , "aa" , "aab" , "aabb" , "aabba"
  • 后缀： "a" , "aa" , "baa" , "abbaa" , "aabbaa"
  • 比较发现，前缀 "aa" 和后缀 "aa" 相等。
• 因此， next[6] = 2 + 1 = 3

十、数组

一维数组

LOC：数组首地址、L：元素大小

第 i 个元素下标从 0 开始：$a_{i}=LOC + i \times L$

第 i 个元素下标从 1 开始：$a_{i}=LOC + (i-1) \times L$

二维数组

LOC：数组首地址、N：行数、M：列数、L：元素大小

• 按行优先存储并且下标从 0 开始： $a_{i,j} = \text{LOC} + (i \times M + j) \times L$
• 按行优先存储并且下标从 1 开始：$a_{i,j} = \text{LOC} + [(i-1) \times M + (j-1)] \times L$
• 按列优先存储并且下标从 0 开始：$a_{i,j} = \text{LOC} + (j \times N + i) \times L$
• 按列优先存储并且下标从 1 开始：$a_{i,j} = \text{LOC} + [(j-1) \times N + (i-1)] \times L$

不明白的话将 i 和 j 分别代入一个值，然后在纸上画出来，比如说 a [2][3]，一个 2 行 3 列的二维数组

二维数组	列 1	列 2	列 3
行 1	$a_{0,0}$	$a_{0,1}$	$a_{0,2}$
行 2	$a_{1,0}$	$a_{1,1}$	$a_{1,2}$

$a_{1,1}$ 上面的行有 i * L 个元素，$a_{1,1}$ 前面还有 j 个元素，然后想加，如果是从 1 开始的就减去 1，就能得到上面的公式。

十一、矩阵

对称矩阵：设有一个 n×n 的矩阵，若矩阵中的任意一个元素都有$A_{i,j}=A_{j,i}$ 则该矩阵为对称矩阵

• 对称矩阵按行存储下三角区和主对角线并且下标从 0（$A_{0,0}$）开始

当 (i≥j) 时：$A_{i,j}=\frac{i(i+1)}{2}+j+1$

当 (i≤j) 时：$A_{i,j}=\frac{j(j+1)}{2}+i+1$

• 对称矩阵按行存储下三角区和主对角线并且下标从 1（$A_{1,1}$）开始

当 (i≥j) 时：$A_{i,j} = \frac{i(i-1)}{2} + j$

当 (i≤j) 时：$A_{i,j} = \frac{j(j-1)}{2} + i$

三对角矩阵按行存储并且下标从 0 开始：$A_{i,j} = 2i + j + 1$

三对角矩阵按行存储并且下标从 1 开始：$A_{i,j} = 2i + j - 2$

三元组顺序表和十字链表是对稀疏矩阵进行压缩存储的方式

十二、树

树的度是指树中所有结点的度的最大值，每个结点的度是有几个分支。

性质：

1. 树中的结点总数等于树中所有结点的度数之和加 1

2. 度为 m 的树中第 i 层上最多有 $m^{i-1}$ 个结点，其中 i ≥ 1

3. 高度为 h 度为 m 的树中至多有 $\frac{m ^ h - 1}{m - 1}$ 个结点

4. 具有 n 个结点、度为 m 的树的最小高度为 $\log_m(n(m-1)+1)$

某树共有 n 个结点，其中所有分支结点的度为 k（即每个非叶子结点的子树数目），则该树中叶子结点的个数为 $\frac{n(k-1)+1}{k}$，这种题，就是假设出一棵树，然后将具体的值代入，就能得到。

十三、二叉树

性质：

1. 第 i 层（i≥1）上最多有 $2^{i-1}$ 个结点

2. 高度为 h 的二叉树最多有 $2^h-1$ 个结点

3. 对于任何一棵二叉树，度为 0 的结点数等于度为 2 的结点数 + 1

4. 具有 n 个结点的完全二叉树的高度为 $log_2 n+1$ 或 $log_2 (n+1)$

5. 计算具有 n 个结点有多少种形态的公式（卡特兰数）：$\frac{C_{2n}^n}{n+1}$

   这个是计算步骤：$C_{n}^m = \frac{n!}{m!(n-m)!}$

6. 一个满二叉树，m 和 n 在同一层的判定是$log_2 m$ = $log_2 n$

十四、二叉树存储结构

顺序存储需要维护结点和左、右孩子的关系：结点编号为 n，则左孩子为 2n，右孩子为 2n + 1。比如下面这棵树，在顺序存储下，第 8 个结点，至少需要 2 * 6 + 1 = 13 个。

        1
       / \
      2   3
     / \ / \
    4  5 6  7
          \
           8

链式存储有二叉链表和三叉链表。对于 n 个结点的二叉树，二叉链表的空指针为 n+1，三叉链表的空指针为 n+2。还以上图为例，二叉链表有 $2 \times 8 + 1 = 17$ 个空指针，三叉链表有$2 \times 8 + 2 = 18$ 个空指针。

十五、二叉树的遍历

遍历名称	访问顺序	字母顺序表示
先序遍历	根 → 左 → 右	DLR
中序遍历	左 → 根 → 右	LDR
后序遍历	左 → 右 → 根	LRD
层序遍历	从上到下、从左往右依次遍历

通过序列构造二叉树必须有中序序列，知道先序序列和后序序列，只能得到树的根结点，不能得到树的中序序列

十六、平衡二叉树和二叉排序树

平衡二叉树：二叉树中的任意个结点的左右子树的高度之差绝对值 ≤ 1，只关注分支结点即可。

二叉排序树：根结点的关键字大于左子树所有结点的关键字，小于右子树的所有结点的关键字。要记得左右子树也是一个二叉排序树。

组合一个二叉排序树：23 31 17 19 11 27 13 90 61，第一个为根结点，然后下一个跟上一个比较，如果小了放左边，如果大了，放右边，左或者右有了就放在它的下一个。

所以就可以得到一句话：从根到任意一个叶子结点的路径上，结点的关键字不能呈现有序排列的特点（23、17、11、13），但是从左到右排列同层次的结点，其关键字可以呈现有序排列的特点。

          23
       /     \
      17     31
     /  \    / \
    11  19  27  90
     \          /
      13       61

回顾：完全二叉树是一种特殊的二叉树，除最后一层外，每一层的节点都必须填满，并且最后一层的节点都靠左对齐。换句话说，如果树的深度为 h，那么从第 1 层到第 h-1 层必须含有$2^{h-1}$ 个节点，第 h 层的节点数可以少于$2^{h-1}$ 个，但必须靠左排列。

中序遍历得到的序列是有序序列。

最坏的查找情况是单枝树（即高度 h 为 n）要查找 h。

十七、最优二叉树（哈夫曼树）

定义：它是一类带权路径最短的树。路径是从树中的一个结点到另一个结点之间的通路，路径上的分支数称为路径长度。

树的路径长度是从树根到每一个叶子结点的路径长度之和。

带权路径是指从该节点到树根之间的路径长度与该结点的权值乘积之和。如下图：权值（3）和边数（2），公式为：

$3 \times 2 + 2 \times 2 + 4 \times 2 + 1 \times 2 = 20$

	  12
     /  \ 
   5     7
  / \   / \ 
 3   2 4   1

WPL = $\sum_{i} w_i \cdot l_i$

• 哈夫曼树中权值越大的结点离根结点越近，权值越小的结点离根结点越远。

• 哈夫曼树只有度为 0 和度为 2 的结点，没有度为 1 的结点。

• n 个权值构造的哈夫曼树具有 2n - 1 个结点。

构造最优二叉树步骤：

1. 从前往后找两个权值最小的。
2. 小左大右。
3. 相加后的新值加入队列的末尾。
4. 如果权值相同的话，从左到右。
5. 用时再调

如何计算哈夫曼编码和压缩比，以下面表格为例，求出 cade 的哈夫曼编码和文档压缩比

字符	a	b	c	d	e
频率（%）	40	10	20	16	14

哈夫曼编码计算步骤：

1. 先根据频率作为权值，将这个最优二叉树构建出来

             [100]
           /       \
        [a:40]      [60]
               /        \
             [24]       [36]
           /      \     /     \
       [b:10]   [e:14] [d:16] [c:20]
   

2. 左子树标上 0，右子树标上 1

             [100]
          0/       \1
        [a:40]      [60]
               0/        \1
             [24]       [36]
           0/      \1     0/     \1
       [b:10]   [e:14] [d:16] [c:20]

3. 从上到下，依次写出，cade = 1110110101

压缩比计算步骤：

1. 计算出等长编码：一共有 5 个字母，所以$2^x \geq 5$，x = 3

2. 计算等长编码：$(40 + 10 + 20 + 16 + 14) \times 3 = 300$

3. 计算哈夫曼等长：先算出每个字母的编码值，然后每个对应的权重 * 位数之和。

   a	b	b	d	e
   0	100	111	110	101

   $40 \times 1 +(10 + 20 + 16 + 14) \times 3 = 220$

4. 最后使用差值除以等长编码$\frac80300 \times 100\% = \frac80300\times 100\% \approx 26.67\%$

十八、二叉树类别

平衡二叉树：二叉树中的任意个结点的左右子树的高度之差绝对值 ≤ 1，只关注分支结点即可。

二叉排序树：根结点的关键字大于左子树所有结点的关键字，小于右子树的所有结点的关键字。要记得左右子树也是一个二叉排序树。

完全二叉树：除最后一层外，每一层的节点都必须填满，并且最后一层的节点都靠左对齐。

• 最少节点数： 最少的节点数是 $2^{h-1}$，即最后一层恰好填满，其余各层都是满的。
• 最多节点数： 最多的节点数是 $2^h - 1$，即每一层都是满的。

最优二叉树（哈夫曼树）：哈夫曼树是一棵带权路径长度最小的树。

• 哈夫曼树中权值越大的结点离根结点越近，权值越小的结点离根结点越远。

• 哈夫曼树只有度为 0 和度为 2 的结点，没有度为 1 的结点。

• n 个权值构造的哈夫曼树具有 2n - 1 个结点。

线索二叉树：一般是个干扰选项。

十九、图的概念

无向图

定义：
顶点之间的边没有方向，边表示两个节点之间的连接关系，彼此是 “互相连接” 的。

特点：

• 边是双向的（但图中不标方向）。
• 适合表示 “关系平等” 的连接，如朋友关系、道路相连等。

简易图示：

  A —— B
   \   /
     C

说明：

• A、B、C 三个点之间通过无方向的边相连。

---

有向图

定义：
图中的边是有方向的，从一个顶点 “指向” 另一个顶点。

特点：

• 每条边都有起点和终点。
• 适合表示 “方向性关系”，比如：A 喜欢 B（不一定 B 喜欢 A）、网页链接等。

简易图示：

  A → B
   ↘  
     C

说明：

• A 指向 B，A 指向 C，但 B 和 C 没有反向连接。

---

无向完全图

定义：
任意两个顶点之间都通过一条无向边直接连接。

特点：

• 如果有 n 个顶点，则有 $\frac{n(n-1)}{2}$ 条边。
• 每对顶点之间都有一条边。

简易图示（以 3 个点为例）：

  A —— B
   \   /
     C

说明：

• A、B、C 三点之间两两连接，边无方向。
• 看起来和普通无向图相似，但这里是 “每一对点” 都连边。

---

有向完全图

定义：
任意两个顶点之间都有两条方向相反的边（即每对顶点之间都有双向连接）。

特点：

• 如果有 n 个顶点，则有$n(n-1)$ 条边。
• 每对顶点之间都互相指向。

简易图示（3 个点）：

  A ↔ B
  ↑   ↓
  C ←→

说明：

• A、B、C 三点之间都互相指向。
• 每两个点之间都有两个方向的边（形成双向箭头）。

---

总结

图类型	所有顶点度数之和 (E 边的数量)
无向图	2E
有向图	2E

图类型	顶点数 n	最少边数	最多边数	说明
无向图	n	$0$	$\frac{n(n-1)}{2}$	无向图可以没有边，最多边数是完全图的边数。
有向图	n	$0$	$n(n-1)$	有向图可以没有边，最多边数是完全有向图的边数。
无向完全图	n	$\frac{n(n-1)}{2}$	$\frac{n(n-1)}{2}$	无向图中每对顶点之间都有一条边。
有向完全图	n	$n(n-1)$	$n(n-1)$	有向图中每对顶点之间都有两条边（两个方向）。
连通图（无向）	n	$n-1$	$\frac{n(n-1)}{2}$	无向图中至少需要 (n-1) 条边才能连通，最多是完全图。
强连通图（有向）	n	$n$	$n(n-1)$	有向图中至少需要 (n) 条边（形成一个有向环），最多是完全有向图。

---

在有向无环图 G 的拓扑序列中，顶点$v_i$ 在顶点$v_j$ 之前，则：

可能存在弧 <$v_i,v_j$>，一定不存在弧 <$v_j,v_i$>。

可能存在$v_i$ 到$v_j$ 的路径，一定不存在$v_j$ 到$v_i$ 的路径

二十、邻接矩阵与邻接表

邻接矩阵

邻接矩阵更适合存储稠密图（边数很多的图），邻接矩阵是一个表示图中顶点之间是否存在边的二维数组，大小是：$n \times n$（n 是图中顶点的个数）。

邻接表

邻接表更适合存储稀疏图（边数很少的图）

跟有向图或者无向图无关

无向图采用邻接表存储有 2e 个表结点（e 为边数）

有向图采用邻接表存储有 n + e 个表结点（n 为结点数，e 为边数）

二十一、图的遍历

图的遍历就是从图中的一个顶点出发，访问图中所有与该顶点 连通的顶点，每个顶点只访问一次。

深度优先遍历（DFS）

• 像 “走迷宫”，一条路走到底，走不通就回退
• 一般使用 递归 或 栈 实现

伪代码：

DFS(v):
    标记 v 已访问
    for 邻接点 w in v 的邻接表:
        if w 未访问:
            DFS(w)

举例

图如下（无向图）：

A —— B —— C
|         |
D ————————

DFS 遍历从 A 开始的访问顺序（可能的一种）： A → B → C → D

解释：

• 从 A 出发
• 找到邻接点 B → 然后从 B 深度访问 C → C 连接 D → 回到 D
• 或者 A → D → C → B（也是合法的，只要每个点访问一次）

---

广度优先遍历（BFS）

• 像 “水波扩散” 或 “分层访问”
• 一层一层地访问邻接点
• 使用 队列 实现

伪代码：

BFS(v):
    初始化队列 Q
    标记 v 已访问
    Q 入队 v
    while Q 非空:
        u = Q 出队
        for 邻接点 w in u 的邻接表:
            if w 未访问:
                标记 w
                Q 入队 w

举例

图如下（无向图）：

A —— B —— C
|         |
D ————————

BFS 遍历从 A 开始访问顺序：A → B → D → C

解释：

• A 的邻接点是 B 和 D（入队）
• 然后访问 B → 再入队 C（D 已入队）
• 然后访问 D（D 的邻居已访问过）
• 最后访问 C

---

总结

比较点	DFS	BFS
数据结构	栈（或递归）	队列
访问顺序	尽可能深入	一层一层地访问
使用场景	拓扑排序、连通分量	最短路径（无权图）等

广度优先遍历（BFS）按层次逐层遍历图的节点。

• 从起始节点开始，首先访问它的所有邻接节点，然后再依次访问这些节点的邻接节点，依次类推，直到遍历完所有可达的节点。
• 广度优先遍历通常用于寻找两个节点间的最短路径或者树的层次遍历等问题。

深度优先遍历（DFS）以深度为优先考虑的策略进行遍历。

• 从起始节点开始，访问一个未访问过的邻接节点，然后再继续递归地访问这个邻接节点的未访问过的邻接节点，直到没有未访问过的邻接节点，然后回溯到上一层节点，继续访问其他未访问的邻接节点。
• 深度优先遍历通常用于寻找图的连通分量、拓扑排序或者生成迷宫等问题。

存储结构	DFS 时间复杂度	BFS 时间复杂度
邻接矩阵	O($n^2$)	O($n^2$)
邻接表	O($n+e$)	O($n+e$)

（其中 n 为顶点数，e 为边数）

注意

使用队列对图进行广度优先遍历

无向连通图的邻接矩阵是对称矩阵

二十二、拓扑序列

在有向无环图 G 的拓扑序列中，顶点$v_i$ 在$v_j$ 之前，则：

• 可能存在弧 <$v_i, v_j$>，一定不存在弧 <$v_j, v_i$>
• 可能存在$v_i$ 到$v_j$ 的路径，一定不存在$v_j$ 到$v_i$ 的路径

对 AOV 网进行拓扑排序的方法如下:

1. 在 AOV 网中选择一个入度为零 (没有前驱) 的顶点且输出它
2. 从网中删除该顶点及与该顶点有关的所有边
3. 重复上述两步，直至网中不存在入度为零的顶点为止。

二十三、查找

主要考的是二分查找

• 静态查找表有：顺序查找，折半（二分）查找，分块查找
• 动态查找表有：二叉排序树，平衡二叉树，B + 树，哈希表

顺序查找方法既适用于顺序存储结构，也适用于链表结构

类型	描述	公式	解释
最多	在最坏情况下，目标元素位于查找表的最后一个位置，或者目标元素不存在。	n	需要逐一比较所有 (n) 个元素才能确定结果。
最少	在最好情况下，目标元素正好是第一个元素，第一次比较就找到目标。	1	目标元素直接命中第一个位置，无需进一步比较。
平均	假设每个元素被查找的概率相等，且查找成功时的平均比较次数为所有可能情况的期望值。	$\frac{n + 1}{2}$	平均情况下，需要比较一半的元素才能找到目标。

二分查找要求顺序存储，元素有序排列

类型	描述	公式	解释
最多	在最坏情况下，目标元素位于查找表的最后一个可能位置，或者目标元素不存在。	$\log_2{n}+1$	每次比较将搜索范围缩小一半，最终需要 次比较才能确定结果。
最少	在最好情况下，目标元素正好是当前中间元素，第一次比较就找到目标。	1	目标元素直接命中中间值，无需进一步分割。
平均	假设每个元素被查找的概率相等，且查找成功时的平均比较次数为所有可能情况的期望值。	$\log_2{(n+1)}-1$	平均情况下，二分查找的比较次数接近于对数级别，但略小于最多比较次数。

二分查找去中值默认下取整，下取整没有正确答案时再考虑上取整。如果题目是给了一组数字问哪个是不可能的就把他画下来，第一个为根结点，然后大的放右边，小的放左边，如果有一层中存在两个结点了那么这个就是不对的。

取中间值得公式为$left+\frac{(right - left)}{2}$

以 [15, 23, 38, 47, 55, 62, 88, 95, 102, 123] 为例子

• left = 0 ， right = 9
• 计算中间值： mid = 0 + (9 - 0) / 2 = 4
• 中间元素： arr[4] = 55

二十四、哈希表

构造哈希函数时应尽量使关键字的所有组成部分都能起作用

一般情况下，冲突处理方法相同的哈希表，其平均查找长度依赖于哈希表的装填因子。哈希表的装填因子（α）定义为

α = \frac{表中装入的记录数}{哈希表的长度}

α 标志着哈希表的装满程度。直观地看，α 越小，发生冲突的可能性就越小：反之，α 越大，表中已填入的记录越多，再填记录时，发生冲突的可能性就越大，则查找时，给定值需与之进行比较的关键字的个数也就越多。

H(Key) = Key \mod p

H (Key)=Key mod p，中 p 的值一般为不大于 n 且最接近 n 的质数

对于某个哈希函数日和两个关键字$K_1$ 和$K_2$，如果$K_1 \neq K_2$，而 H ($K_1$)=H($K_2$)，则称为冲突。具有相同哈希函数值的关键字对该哈希函数来说称为同义词。

警告

设用线性探查法解决冲突构造哈希表，且哈希函数为 H（key）=key% m，若在该哈希表中查找某关键字 e 是成功的且与多个关键字进行了比较，则 （60） 。（2021 年上半年）

（60） A. 这些关键字形成一个有序序列

B. 这些关键字都不是 e 的同义词

C. 这些关键字都是 e 的同义词

D. 这些关键字的第一个可以不是 e 的同义词

二十五、小顶堆与大顶堆

给一个数组例如（2, 8, 7, 1, 3, 5, 6, 4），先把它变成一个树，按照顺序把每一层放满，然后再按照公式调整，就能得到答案。

大顶堆：每个结点的值都大于或等于其左右孩子结点的值。

小顶堆：每个结点的值都小于或等于其左右孩子结点的值。

二十六、排序

排序算法	平均时间复杂度	最坏时间复杂度	最佳时间复杂度	空间复杂度	稳定性
直接插入排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定
希尔排序	$O(n^{1.3})$	$O(n^2)$	$O(n)$	$O(1)$	不稳定
简单选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
堆排序	$O(nlog_2{n})$	$O(nlog_2{n})$	$O(nlog_2{n})$	$O(1)$	不稳定
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定
快速排序	$O(nlog_2{n})$	$O(n^2)$	$O(nlog_2{n})$	$O(log_2{n})$	不稳定
归并排序	$O(nlog_2{n})$	$O(nlog_2{n})$	$O(nlog_2{n})$	$O(n)$	稳定

直接插入排序

直接插入排序（Insertion Sort）是一种简单直观的基于比较的排序算法，其核心思想是通过构建有序序列，逐步将未排序部分的元素插入到已排序部分的正确位置。以下是详细说明：

1. 算法步骤

1. 初始化：将数组的第一个元素视为已排序序列（单个元素自然有序）。
2. 遍历未排序部分：从第二个元素开始，依次将当前元素与已排序序列中的元素从后向前比较。
3. 插入操作：
   • 若当前元素比已排序元素小，则将已排序元素向后移动一位。
   • 重复此过程，直到找到当前元素的正确位置。
4. 插入元素：将当前元素放入正确位置，已排序序列长度增加。
5. 重复：直至所有元素被处理。

---

2. 图解步骤

对数组 [5, 2, 4, 6, 1, 3] 的排序过程：

轮次	已排序部分	当前元素	操作	结果
1	[5]	2	5 > 2，5 后移，插入 2	[2, 5, 4, 6, 1, 3]
2	[2, 5]	4	5 > 4，5 后移；2 < 4，插入 4	[2, 4, 5, 6, 1, 3]
3	[2, 4, 5]	6	5 < 6，直接插入	[2, 4, 5, 6, 1, 3]
4	[2, 4, 5, 6]	1	6,5,4,2 均 > 1，全部后移，插入 1	[1, 2, 4, 5, 6, 3]
5	[1, 2, 4, 5, 6]	3	6,5,4 > 3；2 < 3，插入 3	[1, 2, 3, 4, 5, 6]

---

3. 代码实现（Java）

public void insertionSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return; // 空数组或单元素数组无需排序
    }
    for (int i = 1; i < arr.length; i++) { // 从第二个元素开始
        int key = arr[i]; // 当前待插入的元素
        int j = i - 1;    // 已排序部分的最后一个索引
        // 从后向前扫描，找到 key 的正确位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; // 比 key 大的元素后移
            j--;
        }
        arr[j + 1] = key; // 插入 key 到正确位置
    }
}

---

4. 时间复杂度

• 最优：数组已有序时，仅需比较 n-1 次，无需移动 → O(n)。
• 最差：数组逆序时，每次插入需移动全部已排序元素 → O(n²)。
• 平均：O (n²)。

---

5. 空间复杂度

• O(1)：原地排序，仅需常数级额外空间。

---

6. 稳定性

• 稳定算法：相等元素的相对顺序在排序后保持不变（后插入的不会越过前面的相同元素）。

---

7. 优缺点

• 优点：
  • 实现简单，对小规模或部分有序数据高效。
  • 适合链表等动态数据结构（无需随机访问）。
• 缺点：
  • 大规模数据效率低（平方级复杂度）。

希尔排序

希尔排序（Shell Sort）是 插入排序的改进版本，由 Donald Shell 于 1959 年提出。它通过 分组插入排序（Group Insertion Sort） 的方式，逐步减少间隔（gap），最终使整个数组基本有序，最后进行一次标准的插入排序。

希尔排序的关键在于 “缩小增量排序”（Diminishing Increment Sort）：

1. 分组策略：将数组按一定间隔（gap）分成若干子序列，对每个子序列进行插入排序。
2. 逐步缩小 gap：每次排序后，缩小 gap 值，直到 gap = 1 （即标准的插入排序）。
3. 最终排序：当 gap = 1 时，数组已经基本有序，插入排序的效率很高（接近 O (n)）。、

---

1. 算法步骤

1. 选择初始 gap：通常取 gap = n / 2 （第二轮 gap = gap / 2 ）。
2. 分组插入排序：
   • 对每个子序列（间隔 gap 的元素）进行插入排序。
3. 缩小 gap：
   • 重复上述步骤，直到 gap = 1 ，此时整个数组基本有序。
4. 最终插入排序：
   • 当 gap = 1 时，执行一次标准的插入排序，完成排序。

---

2. 示例（图解）

假设数组 [8, 3, 5, 1, 4, 7, 6, 2] ，初始 gap = 4 ：

轮次	gap	分组方式	排序后数组
1	4	[8,4] , [3,7] , [5,6] , [1,2]	[4, 3, 5, 1, 8, 7, 6, 2]
2	2	[4,5,8,6] , [3,1,7,2]	[4, 1, 5, 2, 6, 3, 8, 7]
3	1	标准插入排序	[1, 2, 3, 4, 5, 6, 7, 8]

3. 代码实现（Java）

public static void shellSort(int[] arr) {
    int n = arr.length;

    // 初始 gap = n/2，并逐步缩小
    for (int gap = n / 2; gap > 0; gap /= 2) {

        // 对每个子序列进行插入排序
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;

            // 插入排序逻辑
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

---

4. 时间复杂度

情况	时间复杂度	说明
最优情况	$O(n)$	数组已经基本有序（gap=1 时接近插入排序的最优情况）
最坏情况	$O(n^2)$	取决于 gap 序列的选择（如使用 gap = n/2, n/4, ..., 1 的原始序列）
平均情况	$O(n^{1.3})$	经验值，实际复杂度与 gap 序列强相关（Hibbard 序列可达 $O(n^{\frac{3}{2}})$）

5. 空间复杂度

• O(1)：原地排序，仅需少量临时变量。

---

6. 稳定性

• 不稳定排序：由于分组交换可能导致相同元素的相对顺序改变。

---

7. 适用场景

✅ 适合中等规模数据（比插入排序更快）。
✅ 适用于部分有序的数据（比冒泡、选择排序高效）。
❌ 不适合超大规模数据（不如快速排序、归并排序高效）。

简单选择排序

简单选择排序（Selection Sort）是一种直观的 基于比较的排序算法，其核心思想是 每次从未排序部分选出最小（或最大）元素，放到已排序部分的末尾。它和 插入排序、冒泡排序 同属于 $O(n^2)$ 排序算法，但相比冒泡排序，它的交换次数更少。

---

1. 核心思想

1. 分界线划分：将数组分为 已排序部分（左侧） 和 未排序部分（右侧）。
2. 选择最小元素：在未排序部分中找到最小元素。
3. 交换位置：将最小元素与未排序部分的第一个元素交换，使其加入已排序部分。
4. 重复执行：直到所有元素排序完成。

---

2. 算法步骤

1. 初始时，已排序部分为空，未排序部分为整个数组。
2. 遍历未排序部分，找到最小元素的下标 minIndex 。
3. 将 arr[minIndex] 与未排序部分的第一个元素 arr[i] 交换。
4. 扩大已排序部分（ i++ ），缩小未排序部分。
5. 重复上述步骤，直到整个数组有序。

---

3. 示例（图解）

以数组 [64, 25, 12, 22, 11] 为例：

轮次	操作	数组状态
初始	未排序：[64, 25, 12, 22, 11]	[64, 25, 12, 22, 11]
1	找到最小 11 ，与 64 交换	[11, 25, 12, 22, 64]
2	找到最小 12 ，与 25 交换	[11, 12, 25, 22, 64]
3	找到最小 22 ，与 25 交换	[11, 12, 22, 25, 64]
4	找到最小 25 ，已在正确位置	[11, 12, 22, 25, 64]
完成	数组已有序	[11, 12, 22, 25, 64]

---

4. Java 实现

public class SelectionSort {

    public static void selectionSort(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            int minIndex = i; // 假设当前未排序部分的第一个是最小的

            // 在未排序部分找到最小元素的下标
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // 交换最小元素到已排序部分的末尾
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        System.out.println("排序前: " + Arrays.toString(arr));

        selectionSort(arr);

        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

---

5. 时间复杂度

情况	时间复杂度	说明
最优情况	$O(n^2)$	即使数组已经有序，仍需完整比较
最坏情况	$O(n^2)$	每次都要扫描剩余未排序部分
平均情况	$O(n^2)$	比较次数固定

注：选择排序的 比较次数固定为 $\frac{n(n-1)}{2}$，不受数据分布影响。

---

6. 空间复杂度

• $O(1)$：原地排序，仅需少量临时变量（如 minIndex , temp ）。

---

7. 稳定性

• 不稳定排序：由于交换可能改变相同元素的相对顺序。
  示例： [5a, 2, 5b, 1] → [1, 2, 5b, 5a] （ 5a 和 5b 顺序改变）。

---

8. 适用场景

✅ 小规模数据（实现简单，代码量少）。
✅ 对交换次数敏感的场景（比冒泡排序交换次数少）。
❌ 不适合大规模数据（$O(n^2)$ 效率低）。

堆排序

堆排序（Heap Sort）是一种 基于完全二叉堆（Heap）数据结构 的高效排序算法，结合了 插入排序（Insertion Sort） 和 归并排序（Merge Sort） 的部分优点：

1. 核心思想

1. 构建最大堆（Max Heap）：
   • 将无序数组调整为一个 最大堆（父节点 ≥ 子节点）。
2. 交换堆顶与末尾元素：
   • 堆顶是当前最大值，将其与数组末尾元素交换。
3. 缩小堆并重新调整：
   • 排除已排序的最大值，对剩余部分重新调整为最大堆。
4. 重复执行：
   • 直到堆大小缩减为 1，排序完成。

---

2. 算法步骤

1. 建堆（Heapify）：
   • 从最后一个非叶子节点（ n/2 - 1 ）开始，自底向上调整，构建最大堆。
2. 排序：
   • 交换堆顶（最大值）与当前堆的最后一个元素。
   • 堆大小减 1，并对新堆顶进行 下沉（Sift Down） 调整。
   • 重复直到堆中只剩一个元素。

---

3. 示例（图解）

以数组 [4, 10, 3, 5, 1] 为例：

步骤 1：构建最大堆

初始数组（完全二叉树形式）：

        4
       / \
      10  3
     / \
    5   1

调整过程：

1. 从最后一个非叶子节点 10 开始：
   • 10 > 5 且 10 > 1 ，无需调整。
2. 调整节点 4 ：
   • 4 < 10 ，交换 4 和 10 ：

        10
       / \
      4   3
     / \
    5   1
   

   • 4 < 5 ，交换 4 和 5 ：

        10
       / \
      5   3
     / \
    4   1
   

   最终最大堆：

        10
       / \
      5   3
     / \
    4   1

步骤 2：排序（交换堆顶与末尾元素）

1. 交换 10 （堆顶）和 1 （末尾）：

        1
       / \
      5   3
     / 
    4 
   

   排序部分： [ , , , , 10]
2. 对 1 进行下沉调整：
   • 1 < 5 ，交换 1 和 5 ：

        5
       / \
      1   3
     / 
    4 
   

   • 1 < 4 ，交换 1 和 4 ：

        5
       / \
      4   3
     / 
    1 
   

3. 交换 5 （堆顶）和 1 （末尾）：

        1
       / \
      4   3
     / 
    5 
   

   排序部分： [ , , , 5, 10]
4. 重复上述过程，直到堆大小为 1。

最终排序结果： [1, 3, 4, 5, 10]

---

4. Java 实现

public class HeapSort {

    public static void heapSort(int[] arr) {
        int n = arr.length;

        // 1. 构建最大堆（从最后一个非叶子节点开始调整）
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 2. 逐个提取堆顶元素（最大值）并调整堆
        for (int i = n - 1; i > 0; i--) {
            // 交换堆顶和当前末尾元素
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 调整剩余堆
            heapify(arr, i, 0);
        }
    }

    // 调整堆（下沉操作）
    private static void heapify(int[] arr, int n, int i) {
        int largest = i;    // 初始化当前节点为最大值
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        // 比较左子节点
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        // 比较右子节点
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // 如果最大值不是当前节点，交换并继续调整
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // 递归调整受影响的子树
            heapify(arr, n, largest);
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 10, 3, 5, 1};
        System.out.println("排序前: " + Arrays.toString(arr));

        heapSort(arr);

        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

输出：

排序前: [4, 10, 3, 5, 1]
排序后: [1, 3, 4, 5, 10]

---

5. 时间复杂度

情况	时间复杂度	说明
最优情况	$O(nlog_2{n})$	数据随机分布
最坏情况	$O(nlog_2{n})$	即使数据逆序，仍需调整堆
平均情况	$O(nlog_2{n})$	稳定高效

---

6. 空间复杂度

• $O(1)$：原地排序，仅需常数级额外空间（如交换变量）。

---

7. 稳定性

• 不稳定排序：
  示例： [3a, 3b, 2] → 建堆时可能交换 3a 和 3b ，导致顺序改变。

---

8. 适用场景

✅ 大规模数据排序（$O(nlog_2{n})$ 效率高）。
✅ 内存受限环境（原地排序，空间复杂度 $O(1)$）。
❌ 需要稳定排序的场景（如数据库索引排序）。

适用场景：

• 数据量较大且对稳定性无要求的排序（如优先级队列、Top K 问题）。
• 工业级应用中，快速排序 通常更快（缓存友好），但堆排序保证最坏 $O(nlog_2{n})$。

冒泡排序

冒泡排序（Bubble Sort）是一种 基于交换的简单排序算法，因其排序过程中较小的元素会像气泡一样逐渐 “浮” 到数组顶端而得名。但是效率不高。

---

1. 核心思想

1. 相邻元素比较：从数组的第一个元素开始，依次比较相邻的两个元素。
2. 交换位置：如果前一个元素比后一个元素大（升序排序），则交换它们的位置。
3. 重复遍历：每一轮遍历会将当前未排序部分的最大元素 “冒泡” 到正确位置。
4. 终止条件：当某一轮遍历没有发生任何交换时，说明数组已经有序，排序结束。

---

2. 算法步骤

1. 外层循环：控制排序轮数，共需 n-1 轮（ n 为数组长度）。
2. 内层循环：比较相邻元素，并根据需要交换位置。
3. 优化：引入标志位 swapped ，若某一轮未发生交换，则提前终止排序。

---

3. 示例（图解）

以数组 [5, 3, 8, 4, 2] 为例：

初始数组：

[5, 3, 8, 4, 2]

第一轮遍历：

1. 比较 5 和 3 → 5 > 3 → 交换 → [3, 5, 8, 4, 2]
2. 比较 5 和 8 → 5 < 8 → 不交换
3. 比较 8 和 4 → 8 > 4 → 交换 → [3, 5, 4, 8, 2]
4. 比较 8 和 2 → 8 > 2 → 交换 → [3, 5, 4, 2, 8]

结果：最大值 8 已 “冒泡” 到末尾。

第二轮遍历：

1. 比较 3 和 5 → 3 < 5 → 不交换
2. 比较 5 和 4 → 5 > 4 → 交换 → [3, 4, 5, 2, 8]
3. 比较 5 和 2 → 5 > 2 → 交换 → [3, 4, 2, 5, 8]

结果：次大值 5 已就位。

第三轮遍历：

1. 比较 3 和 4 → 3 < 4 → 不交换
2. 比较 4 和 2 → 4 > 2 → 交换 → [3, 2, 4, 5, 8]

结果： 4 已就位。

第四轮遍历：

1. 比较 3 和 2 → 3 > 2 → 交换 → [2, 3, 4, 5, 8]
2. 无更多交换，排序完成。

最终结果：

[2, 3, 4, 5, 8]

---

4. Java 实现

public class BubbleSort {

    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;

        for (int i = 0; i < n - 1; i++) {
            swapped = false;

            // 内层循环：比较相邻元素
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换 arr[j] 和 arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }

            // 如果本轮未发生交换，提前终止
            if (!swapped) break;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        System.out.println("排序前: " + Arrays.toString(arr));

        bubbleSort(arr);

        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

输出：

排序前: [5, 3, 8, 4, 2]
排序后: [2, 3, 4, 5, 8]

---

5. 时间复杂度

情况	时间复杂度	说明
最优情况	$O(n)$	数组已经有序，仅需一轮遍历
最坏情况	$O(n^2)$	数组完全逆序，需完整 $\frac{n(n-1)}{2}$ 次比较
平均情况	$O(n^2)$	数据随机分布

注：优化后（ swapped 标志位）的最优时间复杂度可降至 $O(n)$。

---

6. 空间复杂度

• $O(1)$：原地排序，仅需常数级额外空间（如交换变量 temp ）。

---

7. 稳定性

• 稳定排序：只有前一个元素严格大于后一个元素时才交换，相等时不交换。

---

8. 适用场景

✅ 教学示例（算法入门，易于理解）。
✅ 小规模数据（数据量较小时效率尚可）。
❌ 大规模数据（$O(n^2)$ 效率低，工业级应用通常选择更快的算法）。

---

适用场景：

• 数据量极小（如 n < 100 ）或近乎有序的数组。
• 教学演示或算法学习。

快速排序

快速排序（Quick Sort）是一种 基于分治法（Divide and Conquer）的高效排序算法，由 Tony Hoare 于 1959 年提出。它是目前实际应用中最快的通用排序算法之一，平均时间复杂度为 $O(nlog_2{n})$，且具有原地排序的特性。

---

1. 核心思想

1. 选取基准（Pivot）：从数组中选择一个元素作为基准（通常选第一个、最后一个或随机元素）。
2. 分区（Partition）：将数组分为两部分：
   • 左子数组：所有元素 ≤ 基准。
   • 右子数组：所有元素 > 基准。
3. 递归排序：对左右子数组分别递归调用快速排序。
4. 合并结果：由于是原地排序，无需合并操作，数组自然有序。

---

2. 算法步骤

1. 终止条件：如果子数组长度为 0 或 1，直接返回。
2. 分区操作：
   • 初始化基准（如 pivot = arr[high] ）。
   • 使用双指针（ i 和 j ）遍历数组：
     • i 指向左子数组的末尾（初始为 low-1 ）。
     • j 从 low 到 high-1 ，比较 arr[j] 与 pivot 。
     • 若 arr[j] ≤ pivot ，则 i++ 并交换 arr[i] 和 arr[j] 。
   • 最后交换 arr[i+1] 和 pivot ，返回 i+1 作为分界点。
3. 递归调用：
   • 对左子数组 [low, pivot_index-1] 排序。
   • 对右子数组 [pivot_index+1, high] 排序。

---

3. 示例（图解）

以数组 [10, 80, 30, 90, 40, 50, 70] 为例，选择最后一个元素 70 为基准：

初始数组：

[10, 80, 30, 90, 40, 50, 70]

基准 pivot = 70 ， i = -1 ， j 从 0 到 5。

分区过程：

1. j=0 ： 10 ≤ 70 → i=0 ，交换 arr[0] 和 arr[0] （无变化）。
   • 数组： [10, 80, 30, 90, 40, 50, 70]
2. j=1 ： 80 > 70 → 不操作。
3. j=2 ： 30 ≤ 70 → i=1 ，交换 arr[1] 和 arr[2] 。
   • 数组： [10, 30, 80, 90, 40, 50, 70]
4. j=3 ： 90 > 70 → 不操作。
5. j=4 ： 40 ≤ 70 → i=2 ，交换 arr[2] 和 arr[4] 。
   • 数组： [10, 30, 40, 90, 80, 50, 70]
6. j=5 ： 50 ≤ 70 → i=3 ，交换 arr[3] 和 arr[5] 。
   • 数组： [10, 30, 40, 50, 80, 90, 70]

最终交换基准：

• 交换 arr[i+1] （即 arr[4] ）和 pivot （ arr[6] ）。
• 分区结果： [10, 30, 40, 50, 70, 90, 80] ，分界点 pivot_index = 4 。

递归排序左右子数组：

• 左子数组 [10, 30, 40, 50] 和右子数组 [90, 80] 继续排序。

---

4. Java 实现

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 获取分区点
            int pivotIndex = partition(arr, low, high);

            // 递归排序左子数组
            quickSort(arr, low, pivotIndex - 1);

            // 递归排序右子数组
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // 选择最后一个元素作为基准
        int i = low - 1; // i 是左子数组的末尾指针

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                // 交换 arr[i] 和 arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 将基准放到正确位置
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1; // 返回基准的最终位置
    }

    public static void main(String[] args) {
        int[] arr = {10, 80, 30, 90, 40, 50, 70};
        System.out.println("排序前: " + Arrays.toString(arr));

        quickSort(arr, 0, arr.length - 1);

        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

输出：

排序前: [10, 80, 30, 90, 40, 50, 70]
排序后: [10, 30, 40, 50, 70, 80, 90]

---

5. 时间复杂度

情况	时间复杂度	说明
最优情况	$O(nlog_2{n})$	每次分区平衡（如基准选中位数）
最坏情况	$O(n^2)$	每次分区极不平衡（如数组已有序，基准选首 / 末元素）
平均情况	$O(nlog_2{n})$	随机化基准或三数取中法可避免最坏情况

注：通过随机选择基准或三数取中法（Median-of-Three），可大幅降低最坏情况概率。

---

6. 空间复杂度

• $O(log_2{n})$：递归调用栈的深度（最坏情况下为 $O(n)$）。

---

7. 稳定性

• 不稳定排序：分区过程中可能改变相等元素的相对顺序（如 [3a, 2, 3b] 排序后可能变为 [2, 3b, 3a] ）。

---

8. 适用场景

✅ 大规模数据排序（平均 $O(log_2{n})$ 效率高）。
✅ 内存敏感环境（原地排序，空间复杂度低）。
❌ 需要稳定排序的场景（如数据库索引）。

---

适用场景：

• 通用排序（如 Java 的 Arrays.sort() 对基本类型使用快速排序变体）。
• 数据量大且对稳定性无要求的场景。

归并排序

归并排序（Merge Sort）是一种 基于分治法（Divide and Conquer）的高效、稳定的排序算法。它的核心思想是将数组递归拆分为最小的子数组（单个元素），然后逐步合并成有序数组。归并排序的时间复杂度为 $O(nlog_2{n})$，且能保持稳定性，适用于大规模数据排序。

---

1. 核心思想

1. 分治策略：
   • 分解（Divide）：将数组递归地分成两半，直到每个子数组只包含一个元素。
   • 合并（Merge）：将两个已排序的子数组合并为一个有序数组。
2. 稳定性：合并时，如果两个元素相等，优先保留左侧子数组的元素，确保相对顺序不变。

---

2. 算法步骤

1. 递归分解：
   • 计算中点 mid = low + (high - low) / 2 。
   • 对左子数组 [low, mid] 递归调用归并排序。
   • 对右子数组 [mid+1, high] 递归调用归并排序。
2. 合并有序子数组：
   • 初始化临时数组 temp 和双指针 i （左子数组）、 j （右子数组）。
   • 比较 arr[i] 和 arr[j] ，将较小的放入 temp 。
   • 将剩余未合并的元素直接拷贝到 temp 。
   • 将 temp 复制回原数组 arr 。

---

3. 示例（图解）

以数组 [38, 27, 43, 3, 9, 82, 10] 为例：

分解过程：

[38, 27, 43, 3, 9, 82, 10]
→ [38, 27, 43] 和 [3, 9, 82, 10]
→ [38], [27, 43], [3, 9], [82, 10]
→ [38], [27], [43], [3], [9], [82], [10]（单元素子数组）

合并过程：

1. 合并 [27] 和 [43] → [27, 43]
2. 合并 [38] 和 [27, 43] → [27, 38, 43]
3. 合并 [3] 和 [9] → [3, 9]
4. 合并 [82] 和 [10] → [10, 82]
5. 合并 [3, 9] 和 [10, 82] → [3, 9, 10, 82]
6. 最终合并 [27, 38, 43] 和 [3, 9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

---

4. Java 实现

public class MergeSort {

    public static void mergeSort(int[] arr, int low, int high) {
        if (low < high) {
            int mid = low + (high - low) / 2;

            // 递归排序左子数组
            mergeSort(arr, low, mid);

            // 递归排序右子数组
            mergeSort(arr, mid + 1, high);

            // 合并两个有序子数组
            merge(arr, low, mid, high);
        }
    }

    private static void merge(int[] arr, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;     // 左子数组指针
        int j = mid + 1; // 右子数组指针
        int k = 0;       // temp 数组指针

        // 合并两个子数组
        while (i <= mid && j <= high) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        // 拷贝左子数组剩余元素
        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        // 拷贝右子数组剩余元素
        while (j <= high) {
            temp[k++] = arr[j++];
        }

        // 将 temp 复制回原数组
        System.arraycopy(temp, 0, arr, low, temp.length);
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("排序前: " + Arrays.toString(arr));

        mergeSort(arr, 0, arr.length - 1);

        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

输出：

排序前: [38, 27, 43, 3, 9, 82, 10]
排序后: [3, 9, 10, 27, 38, 43, 82]

---

5. 时间复杂度

情况	时间复杂度	说明
最优情况	$O(nlog_2{n})$	数组完全无序或随机分布
最坏情况	$O(nlog_2{n})$	即使数组已有序，仍需完整分解和合并
平均情况	$O(nlog_2{n})$	稳定高效，适合大规模数据

注：归并排序的时间复杂度始终为 $O(nlog_2{n})$，但需要额外空间。

---

6. 空间复杂度

• $O(n)$：需额外临时数组存储合并结果（递归栈空间为 $O(\log n)$）。

---

7. 稳定性

• 稳定排序：合并时优先保留左侧子数组的相等元素。

---

8. 适用场景

✅ 大规模数据排序（时间复杂度稳定为 $O(nlog_2{n})$）。
✅ 需要稳定排序的场景（如数据库索引、对象排序）。
✅ 外部排序（数据量超过内存时，可分块排序后合并）。
❌ 内存敏感环境（需 $O(n)$ 额外空间）。

---

适用场景：

• 需要稳定排序（如对象排序、数据库操作）。
• 数据量较大且内存充足时。