2. 基本非数值算法

# 查找

# 查找基本概念

平均查找长度（ASL） 是衡量查找算法效率的重要指标，其计算公式为：

$ASL = \sum P_i C_i$

其中， $P_i$ 是第 $i$ 条记录的查找概率， $C_i$ 是第 $i$ 条记录的查找长度。

# 线性表查找

线性表查找主要包括顺序查找和折半查找。不同数据结构的线性表在查找、插入和删除操作上的效率差异显著：

数据结构	查找	插入	删除
无序顺序表	$O(n)$	$O(1)$	$O(n)$
无序线性链表	$O(n)$	$O(1)$	$O(n)$
有序顺序表	$O(lgn)$	$O(n)$	$O(n)$
有序线性链表	$O(n)$	$O(n)$	$O(n)$

# 索引查找

索引查找的基本思想是利用索引表来快速定位数据子表。其关键在于设计高效的索引函数。

索引的存储方式包括：

顺序索引—顺序存储
顺序索引—链接存储
链接索引—顺序存储
链接索引—链接存储

此外，还有多重索引和分块查找（索引顺序查找） 等方法。

索引文件可分为：

单关键字索引
- 稠密索引：每个记录都有一个索引项。
- 稀疏索引：只为部分记录建立索引项。
多关键字索引
- 多重链表文件：包含主索引表、辅索引表、主关键字和次关键字。
- 倒排文件：也包含主索引表、辅索引表、主关键字和次关键字，但组织方式不同。

# 查找树

# 二叉搜索树（BST）

二叉搜索树（BST） 的特性是中序遍历结果为递增序列。

基本操作：

查找
插入
构造
删除：
- 删除叶子结点：直接删除。
- 删除只有左子树或右子树的结点：用其非空子树的根结点替代。
- 删除左右子树都非空的结点：用其中序前驱或后继结点替代。

效率：

	查找	插入
平均	$O(lgn)$	$O(lgn)$
最坏	$O(n)$	$O(n)$

旋转操作：

左旋转：将目标结点与其右孩子逆时针旋转，常用于调整平衡。
右旋转：将目标结点与其左孩子顺时针旋转，常用于调整平衡。

# 平衡二叉树

平衡二叉树旨在解决BST在最坏情况下效率低的问题。

AVL树：任意结点的左子树和右子树的高度差不超过1。
- 平衡因子：左子树高度减去右子树高度。
- 插入操作：插入新结点后，需从该位置向上回溯，检查并调整平衡。不平衡时，根据三个关键结点的位置关系进行单旋转（直线情况）或双旋转（折线情况）。
红黑树：一种自平衡的二叉搜索树，通过对结点着色（红或黑）来维护平衡。

# 多路平衡动态查找

B树：一种多路平衡查找树，特别适合磁盘等外部存储。

# 散列（哈希）

散列是一种将关键字直接映射到存储地址的技术。

# 散列函数

散列函数负责将关键字转换为散列地址，常用的方法有：

简单/随机散列函数
乘法散列函数/模散列函数
数学分析法
平方取中法
折叠法：
- 移位法
- 分界法

# 冲突处理

当多个关键字映射到同一个地址时，需要处理冲突。

链地址法：为每个散列地址维护一个链表来存储冲突的关键字，通常需要额外 $M$ 个链表空间， $M$ 大约为关键字总数的 1/5 到 1/10。
开放定址法：当发生冲突时，通过探测下一个空闲位置来解决。
- 线性探测法：按固定步长（通常为1）向后查找，要求表不能达到半满状态。删除时需要增加删除标志。
- 双重散列：使用第二个散列函数来决定探测的步长，要求第二个散列函数的值不能为0且与表长互素。

# 散列应用

Karp-Rabin 匹配算法：利用散列思想进行字符串匹配。
消息摘要（哈希）：
- MD系列算法：如MD2、MD4、MD5。
- SHA系列算法：如SHA、SHA-1。
- 生日攻击：利用哈希函数的特性进行密码学攻击。

# 排序

# 排序基本概念

数据表：待排序的数据集合。
关键码：用于排序的依据。
稳定性：排序后，如果关键码相同的记录的相对次序没有改变，则称该排序算法是稳定的。
内排序：数据全部在内存中完成排序。
外排序：数据量过大，无法一次装入内存，需要借助外部存储进行排序。
时间开销：通常以比较次数和移动（交换）次数来衡量。

# 简单排序方法

冒泡排序：通过相邻元素的反复比较和交换来完成排序，可增加标记来优化，若一趟遍历没有交换，则表示已有序。
插入排序：
- 直接插入排序：将新元素插入到已排序序列的正确位置。
- 折半插入排序：使用二分查找来确定插入位置，减少比较次数。
- 希尔排序：对直接插入排序的改进，通过分组进行多次排序，逐步减小增量。
选择排序：每次从未排序序列中找到最小（或最大）元素，放到已排序序列的末尾。

效率对比：

排序方法	比较次数（最少）	比较次数（最多）	移动次数（最少）	移动次数（最多）
冒泡排序	$n(n-1)/2$	$n(n-1)/2$	$0$	$n(n-1)$
改进的冒泡排序	$n-1$	$n(n-1)/2$	$0$	$n(n-1)$
直接插入排序	$n-1$	$n(n-1)/2$	$0$	$n(n-1)/2$
折半插入排序	$nlog_2n$	$nlog_2n$	$0$	$n(n-1)/2$
希尔排序	/	/	$0$	/
选择排序	$n(n-1)/2$	$n(n-1)/2$	$0$	$2n$

# 高级排序方法

快速排序：
- 划分操作：选择一个基准元素，将数组分为两部分，左边小于基准，右边大于基准。
- 中间元素法：一种选择基准元素的方法。
归并排序：
- 自底向上：从小子序列开始合并。
- 自顶向下：递归地将序列一分为二，直到每个子序列只包含一个元素，然后进行合并。
堆排序：
- 建堆：根据排序顺序构建最大堆（升序）或最小堆（降序）。
- 排序：将堆顶元素与末尾元素交换，然后对剩余元素重新进行堆化，重复此过程。