#非数值算法
##查找
查找算法的复杂性：关键字/数据规模
查找表（Search Table）是由同一类型数据元素构成的集合
平均查找长度：在查找过程中，为确定目标在查找表中的位置，需要进行关键字比较次数的期望值
ASL =ΣPiCi
##顺序查找与索引查找
####顺序查找
(顺序查找过于简单不再叙述)
对顺序表顺序查找
折半查找
编者按：折半查找就是二分搜索，是一种优化的顺序表查找算法（我也不知道说的对不对）
折半查找可以用一个二叉树结构来描述
对于一次查找,无论成功还是失败，折半查找需要的比较次数不会超过log2 N
不同表示线性表的查找效率比较
###索引查找
将有n 个结点的线性表划分为m 个子表，分别存储各子表
另设一个有m 个结点（索引项）的索引表，每个结点存子表第一个结点的地址及相关信息
索引存储方式
索引表——顺序表或链表
子表——顺序表或链表
索引表特点：表不大，表中元素不常变动
适合用顺序表来表示索引表
索引表为顺序表 子表也为顺序表情况
索引查找比全表顺序查找效率高
索引表采用顺序表 子表采用链表情况
优点：
索引表结构简单，便于查找
子表结点插入、删除不需要移动表中元素
多重索引：当索引表很大时，对索引表再做索引
####分块查找
分块查找也称索引顺序查找，是顺序查找的改进
把线性表顺序划分为若干个子表（块）后满足
子表之间递增（或递减）有序，即后一子表的每一项大于前一子表的所有项
块内元素可以无序
###多关键字索引文件结构
多重表文件
次关键字项：经常需要对其查询的数据项（一项或多项）
次关键字：每个记录的次关键字项的值
多重链表文件结构：
1 主文件为顺序文件
2 对主关键字建立索引表，称为主索引表
3 主文件中对每个次关键字项设一指针域，用以链接相同关键字的记录（单链表）
4 对每个次关键字分别建立索引表，称为辅索引表
倒排文件
倒排文件也是一种多关键字索引文件结构,适用于多关键字查询,与多重链表文件相同之处：主文件+主索引表+辅索引表
优点：处理多关键字查询时，通过集合运算直接得到结果
##二叉搜索树 二叉搜索树（BST：Binary SearchTree）或者是一棵空树，或者是具有下列性质的二叉树：
1 每个结点有一个关键字（Key）
2 任意结点关键字大于等于该结点左子树中所有结点含有的关键字
3 同时该结点的关键字小于等于右子树中所有结点含有的关键字
二叉搜索树的插入过程类似于搜索，在搜索失败后执行插入操作
性能特性
完美的平衡树是极为罕见的，高度不平衡的树也不多见
二叉搜索树中的旋转操作
旋转使一棵树中，结点和结点的一个子孙互换角色，但仍然保持结点关键字之间的次序
右旋转（Right Rotation）涉及到结点及其左孩子
左旋转（Right Rotation）涉及到结点及其右孩子
更多的二叉搜索树
高度平衡的二叉搜索树——AVL树
实用的比较平衡的二叉搜索树——红黑树
多路平衡的动态查找结构——B-树
##散列
散列表（Hash）是将一组关键字映射到一个有限的、地址连续的区间上，并以关键字在地址集中的“像”作为相应记录在表中的存储位置
散列表的冗余度和冲突是一对矛盾
散列函数把关键字映射为存储地址
散列函数应是简单的，能在较短的时间内计算出结果
散列函数的定义域必须包括需要存储的全部关键码，如果散列表允许有m 个地址，其值域必须在0 到m - 1 之间
理想的散列函数应近似为随机的，对每一个输入，相应的输出在值域上是等概的
####三种方法
数字分析法
仅适用于事先知道表中所有关键码每一位数值的分布情况，完全依赖于关键码集合；若换一个关键码集合，需重新选择
平方取中法
先计算构成关键码的标识符的内码的平方, 然后按照散列表的大小取中间的若干位作为散列地址
折叠法
把关键码自左到右分成位数相等的几部分，每部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些
把这些部分的数据叠加起来,就可以得到具有该关键码的记录的散列地址
####冲突问题
链地址法
两个关键字散列到同一地址，也就是冲突问题
最简单的方法是对每个散列地址建立一个链表，将散列到同一地址的不同关键字存入相应的链表中，这种方法称为链地址法
开放地址法
对表长M 大于元素数目N 的情况，依靠空的存储空间来解决冲突问题，这类方法被称为开放地址法
N 为元素数目，M 为表长，定义负载因子α= N/M
散列表的查找
查找过程和建表过程一致
假设采用开放定址处理冲突，对于给定值k，计算散列地址
i = Hash (k)
散列表的删除
在开放定址散列表中，直接对元素进行删除是不行的
双重散列
双重散列不是检查冲突点后面每一个表位置，而是采用第二个散列函数得到一个固定增量序列用于探测序列
##排序-《数据结构与算法》7.1、7.2
排序的时间开销是衡量算法好坏的最重要的标志
算法执行时所需的附加存储：评价算法好坏的另一标准
###冒泡排序
（过于简单不做赘述）
最坏情况：
###插入排序
直接插入
折半插入
希尔（Shell）排序
直接插入
平均情况下，直接插入排序约需要n^2/4 次比较操作和半交换操作
折半插入
插入排序算法中，在插入第k 个元素时，前k-1 个元素组成的序列已经是有序的，可以利用折半查找法寻找的第k-1 个插入位置
长度为k 的序列，折半查找需要经过log2 k+ 1 次比较
n 个对象用折半插入排序需要进行的比较次数约为nlog2n
总的时间复杂度仍然是O（n^2）
希尔排序
编者按：就是有步长的排序。。我是这么觉得的..
好的步长序列：1; 8; 23; 77; 281; 1073 hi=4^(i+1) +3×2^i+1
###快速排序 -《数据结构与算法》7.3
将待排序序列a 划分为两个部分，满足下述条件
a [i] 位于它在序列中的正确位置
前面的元素a [l] ~ a [i-1] 都比a [i] 小
后面的元素a [i + 1] ~a [h] 都比a [i] 大
然后分别对两个部分进行划分
每次划分都至少将一个元素放在它最终应该位于的正确位置，直至所有元素都排序完成
其中的划分操作
l 和r 为序列的第一个和最后一个元素，v 表示划分元素的值，i 表示左侧指针，j 表示右侧指针
选择a [r] 作为划分元素—，划分后位于正确位置
从序列的最左边向中间扫描，找到一个比划分元素大的元素
从序列的最右边向中间扫描，找到一个比划分元素小的元素
交换这两个元素
当扫描指针i 和j 相遇时，和划分元素交换，划分完成
性能分析：最好情况时间复杂度为O(N log2N)
But
快速排序平均情况下需要lgN 的递归栈，但在最坏情况下可以达到N
###归并排序 -《数据结构与算法》7.4
归并是将两个或两个以上的有序表合并成一个新的有序表
，二路归并时间复杂度为O(N)
自底向上的归并排序
自底向上归并排序对整个文件进行m-m 的归并操作，每次m 的值都变成两倍
自底向上归并排序中，每一步进行归并排序的子序列的大小是2 的幂数，最后一个子序列的大小是一个例外
时间复杂度为O(N log2 N)
自顶向下的归并排序
可用递归实现，原理相同不再赘述。
基本排序方法在平均情况下的时间复杂度是O（N^2）
高级排序方法在平均情况下的时间复杂度是O(N logN)
就平均性能来说，快速排序比归并排序好
归并排序是稳定的，快速排序是不稳定的，性能可能退化
可以参考B站上的热门视频15种排序