查找算法
zKing 2018-11-19 专业知识
# 顺序查找（线性查找）
# 方法
用逐一比较的方法顺序查找关键字
# 性能分析
- 顺序查找平均查找长度为：（n+1）/2
- 时间效率为： O（n）
# 优点
算法简单，适应面广，对查找表的结构没有要求
# 缺点
在n值较大时，平均查找长度较大，查找效率低
# 折半查找（二分/对分 查找）
# 先给数据排序，形成有序表，把待查数据值与查找范围的中间元素值进行比较，会有四种情况出现：
1.待查找数值与中间元素值相等，返回中间元素值的索引 2.待查找数值比中间元素值小，则以整个查找范围的前半部分作为新的查找范围，执行 1 ，直到找到相等的值 3.待查找数值比中间元素值大，则以整个查找范围的后半部分作为新的查找范围，执行 1 ，直到找到相等的值 4.如果最后找不到相等的值，则返回错误提示信息
# 平均查找长度
[ log2（n+1）]-1
# 前提
查找表需要进行顺序存储并且按关键字有序排列
# 注意点
适用于表不易变动，且又经常进行查找的情况 求中间元素的下标时，不采用四舍五入的方法，而是直接取整
# 分块查找（索引顺序查找）
- 性能介于顺序查找和折半查找之间
- 在分块查找过程中，首先把表分成若干快，每一块章的关键字不一定有序，但块之间是有序的。即后一块中所有记录的关键字均大于前一个块中最大的关键字，还建立了一个索引表，索引表按关键字有序排列
- 查找步骤分两步进行
- 对索引表使用折半查找法（因为索引表是有序表）；
- 确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）
# 散列表（哈希表）
# 基本思想
已知关键字集合U，最大关键字为m，设计一个函数Hash，它以关键字为自变量，关键字的存储地址因变量，将关键字映射到一个有限的、地址连续的区间 T0....n-1中，这个区间就成为散列表，散列查找中使用的转换函数称为散列函数
# 基本思路
当我知道key值以后，我就可以直接计算出这个元素在集合中的位置，根本不需要一次又一次的查找！
# 散列冲突解决办法
- 开发定址法
- 如果遇到冲突的时候怎么办呢？就找hash表剩下空余的空间，找到空余的空间然后插入。
- 开发定址法的原理是遇到冲突的时候查找顺着原来哈希地址查找下一个空闲地址然后插入，但是也有一个问题就是如果空间不足，那他无法处理冲突也无法插入数据，因此需要装填因子(空间/插入数据)>=1
- 链地址法
- 链地址法的原理时如果遇到冲突，他就会在原地址新建一个空间，然后以链表结点的形式插入到该空间。