顺序查找

基本思想

顺序查找也称线性查找，通过遍历线性表来查找需要的值，属无序查找算法

如果成功则返回地址，反之给予错误反馈

Code

时间复杂度：O(n)

线性查找 适合 顺序存储 || 链接存储 的线性表

二分查找

基本思想

二分查找也叫折半查找，前提是需要有序表顺序存储，属有序查找算法

顾名思义，通过将有序表折半查询

Code

排序：

此处使用 Shell Sort >了解更多请访问：十大经典排序算法总结 >

二分查找：

时间复杂度：O(log2 n)

二分查找 只适合静态操作，每次数据的变动都将带来不少的工作量

插值查找

基本思想

插值查 找基于二分查找算法，主要将查找点的选择改进为自适应选择；当然，差值查找也属于有序查找。

二分查找主要将有序线性表折半，但当数据在远离中心位置时便会浪费很多资源，我们可以通过预估 key 在 Linear Table 中的大概位置来实现自适应

Code

同样需要先排序 请见：十大经典排序算法总结

插值查找：

时间复杂度：O(logn)

插值查找 适合 Linear Table 较长、关键字分布均匀的情况，插值查找算法的平均性能比折半查找要好的多，但，反之插值查找则未必是个合适的选择

斐波那契查找

基本思想

斐波那契查找 也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和）

黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为 1:0.618 或 1.618:1

Code

同样需要先排序 请见：十大经典排序算法总结

斐波那契查找：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-35OfpwaY-1637567659623)(http://r2cqrixd5.hn-bkt.clouddn.com/notes/images/202111102025322.png)]

时间复杂度：O(log2 n)

分块查询

基本思想

将 n 个数据元素"按块有序"划分为 m 块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第 1 块中任一元素的关键字都必须小于第 2 块中任一元素的关键字；而第 2 块中任一元素又都必须小于第 3 块中的任一元素

分块查找是结合二分查找和顺序查找

在分块查找里有索引表和分块的概念。

分块查找又称索引顺序查找，它是顺序查找的一种改进方法。

Code

时间复杂度：O(log2 b +n/b)

哈希查找

基本思想

如果所有的键都是整数，可以使用一个简单的无序数组，将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值这

是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键

Code

时间复杂度：O(1)

树类查找

正在学习，待更新

总结