查找

线性（顺序）关系：数据项保存在列表这样的集合中。

顺序查找：按照顺序来访问和查找数据项；针对无序表当所要找的数据不在表中时查找需要遍历整个列表，而对于有序表可以设置一个提前结束标志减少计算量。但无论是有序表还是无序表其算法复杂度都为O(n)。

二分查找（binary search）：对于有序表可以从中间项开始匹配，不断缩小表的规模知道找到数据的位置。二分查找法也体现了分治算法。因此二分查找法可以用递归实现。算法复杂度为O(log n)。

def binarySearch(alist,item):  #二分查找的递归实现
......
midpoint = len(alist)//2
if alist[midpoint]==item:
    return True
else:   #减小规模，调用自身
    if item <alist[midpoint]:
        return binarySearch(alist[:midpoint],item)
    else:
        return binarySearch(alist[midpoint+1:],item)

对于两种查找算法，需要根据实际的应用情况进行选择。

排序

冒泡排序（bubble sort）:两两相邻的数据进行比较，多趟之后即可完成排序。与在c语言中交换两个位置的值需要中间变量不同，python中可以使用alist[i],alist[i+1]=alist[i+1],alist[i]语句完成。算法每趟的比较次数由n-1不断递减，因此算法复杂度为O(n^2)。

冒泡排序常作为其他算法的对比基准（妥妥的工具人🙃），其中的对次比对交换操作时无效的。优势在于无需额外储存空间的开销。
改进的冒泡排序：当某次比对未发生交换，便说明比对完成，可以提前结束。
```
def shortBubbleSort(alist):
    ......
    exchange = False
    for i in range(passnum):
        if alist[i]>alist[i+1]:
            exchange = True
            alist[i],alist[i+1]=alist[i+1],alist[i]
        passnum = passnum-1
```
选择排序(Selection Sort)：对冒泡算法中,每趟只进行一次交换。先记录最大项所在的位置再交换。

插入排序（Insertion Sort）:复杂度仍为O(n^2);是中唯持一个已排好序的子列表，其位置始终在列表的前部。并将其逐步扩大只全表。列表越接近有序，插入排序的对比次数就越少。

def insertionSort(alist):
......
while position > 0 and alist[position-1]>currentvalue:
    alist[position]=alist[position-1]
    position = position - 1
    #每次与左侧的项进行比较，如果左侧的值大就将其右移，依次循环直到左侧值更小，在之前的空位中插入。
alist[position]=currentvalue

谢尔排序（Shell Sort）:以“间隔”划分子列表，每个子列表执行插入排序，从而减少整体排序对比的次数。最后再进行标准的插入排序。减少了插入排序中无效的比对，介于O(n)于O(n^2)之间。

分治思想的排序算法

归并排序（Merge Sort）：不断将数据表分裂为原来的一半，直到表中仅有一个数据项。之后再从最小规模开始排序（两个列表中小的先放，迭代，最后归并剩余项）直到完成这个列表的排序。

总体来说分为分裂和归并两个过程，算法复杂度分别为O(log n)和O(n)。但会占用更多的储存空间。
快速排序（Quick Sort）:依据“中值”将数据项分为两半，排序。不断分解至仅有一个数据项。算法复杂度取决于“中值”选取的情况，综合为O(log n)，但不需要额外的储存空间。“中值”选取中很难取得列表中准确的中值（真要准确的中值不还得排序😐），因此只能尽可能通过各种方法使选取的值与“中值”接近。

分裂方法：左标向右移动，直到遇到比中值大的左标；同时右标向右移动，直到遇到比中值小的。将左右标指向的值交换并继续向前移动。当左标到达右标的右侧，右标所指位置即为“中值”。

散列（Hashing）

散列可以使查找算法的复杂度降到O(1)，散列表(hash table)包含用来储存数据的槽(slot)以及槽对应的唯一的名称。槽被数据项占据的比例称为负载因子。

数据与槽名称通过散列函数来对应。可以通过除余数来实现槽号与槽数据项的对应，但当要存储的两个数字余数相同时便会产生冲突。

如果一个散列函数能不会造成冲突便称之为完美散列函数。完美散列函数可以用于数据校验。将散列值看作槽中信息的摘要，由于该摘要具有唯一性因此可以通过摘要对比信息的异同。要具备数据校验的函数应具有以下特性；压缩性、易计算性、抗修改性和抗冲突性。

近似完美散列函数MD5,SHA。

区块链

区块链是一种分布式数据库，具有去中心化的特点。区块链由区块(block)组成。每个区块中包含着头(head)和体(body)。头中记录着一些元数据和链接到前一个区块的信息（生成时间、前一个区块的散列值）。

区块链具有不可修改性。由于区块链的分布式的性质，同步速度较慢因此新区快的添加速度被限制。

PS:每次虚拟货币涨的时候，硬件价格便会水涨船高，加上黄牛党的推波助澜，DIY玩家苦不堪言。

散列函数的设计

折叠法：对数据分段、相加、求余得到槽号。通过哥数反转的方法进行微调。
平方取中法：数据平方、取中间两位、求余（相比折叠法，计算量提高）。

特殊情况
- 对于非数项可通过ASCⅡ表进行转换。 - 对于变为词，加入权重因子

散列函数在设计时盈尽量简单并减少冲突。

冲突解决方案

再找一个空槽放置冲突数据（开放定址、再散列）。

线性探测：向后逐个寻找空槽，查找时顺序查找。缺点：有聚集趋势。
跳跃式探测；选择固定步长或逐步变化进行探测。固定步长取值时不能被散列表大小整除，否则会产生周期。

数据项链：槽扩展为容纳数据项的集合。这会延长查找的时间

引用

数据结构与算法Python版_中国大学MOOC(慕课)