顺序查找

顺序查找（Sequential Search）又称线性查找。从表中第一个(或最后一个)记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，如果查找到表中最后一个元素，还没有找到，则查找不成功。

二分查找

二分查找（Binary Search）又称折半查找。它的前提是线性表中的记录必须是关键码有序，线性表必须采用顺序存储。折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。

插值查找(Interpolation Search)

基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。即根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式mid=low+(key-a[low])/(a[high]-a[low])(high-low)，替换了二分查找的计算公式mid=low+1/2(high-low)。

这样的好处在于，对表长较长，且关键字分布比较均匀，插值查找算法的平均性能要比折半查找要好的多。但是如果表中关键字分布极端不均匀，那么插值查找还不如折半查找呢。

斐波那契查找(Fibonacci Search)

也是一种改进的二分查找，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。

插入排序

直接插入排序

具体算法：

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；

定义

线性表（Linear List）是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用n表示，n>=0。当n=0时，表示线性表是一个
空表。设序列中第i个元素为a₁（1 ≤ i ≤ n），则线性表的一般表示为：

(a₁,a₂,a₃,…,a_i,…,a_n)

特性

• 元素在位置上是有序的
• 长度是可变的

回溯法（Back Tracking Method）（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。
但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，
而满足回溯条件的某个状态的点称为“回溯点”。

1
2
3
4
5
6
7
8
9
10

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

参考