原书作者 Aditya Bhargava
1 算法简介
1.1 二分法查找
二分法查找，正是猜数字游戏的玩法：A从1-100中随机挑一个数，B来猜，A返回B猜的数是大了还是小了，最快的一种方法就是二分法（猜50-->小了，接下来猜75……）
二分法查找速度.png
def binary_search(list, item):
low = 0
high = len(list)-1
while low <= high:
mid = int(round((low + high)/2)) #←---就检查中间的元素
guess = list[mid]
print(guess)
if guess == item: #←--------找到了元素
return mid
if guess > item:
print('←-------------猜的数字大了')
high = mid - 1
else:
print('←--------------猜的数字小了')
low = mid + 1
return None #←--------------------没有指定的元素
#测试
my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3))
1.2 算法运行时间
不同的算法，运行时间差异很大。
简单查找与二分查找.png
五种最常见的算法运行时间
- O(logn)，也叫对数时间，如二分查找。
- O(n)，也叫线性时间，如简单查找。
- O(n * logn)，如快速排序(后续笔记)
- O(n^2)，选择排序（后续笔记）——一种速度较慢的排序算法。
- O(n!)，如旅行商问题。
image.png
2 选择排序
2.1 数组和链表
数组就是一列相邻的数据，位置关系固定，查找(读取很快)，要插入1个数据时，必需把后面的数据全部移动一位；但如果内存中的连续空位不够时就比较麻烦；
链表中中每个元素会记录下一个元素的位置，所以插入很好操作——只需修改一个指向记录。删除操作类似的，也只需要更改某下一个元素的指向位置即可。
- 计算机内存犹如一大堆抽屉。
- 需要存储多个元素时，可使用数组或链表。
- 数组的元素都在一起。
- 链表的元素是分开的，链表中的元素可存储在内存的任何地方，其中每个元素都存储了下一个元素的地址。
- 数组的读取速度很快。
- 链表的插入和删除速度很快。
image.png
2.2 选择排序
选择排序：遍历这个列表，找出播放次数最多的乐队，并将该乐队添加到一个新列表中。接下来继续该操作(找到第二多的乐队)，最终得到一个有序列表。
从大到小排序-选择排序
每次操作需要针对剩余的n个元素(n,n-1,……1，平均为n1/2)，共操作n次，故算法时间为O(nn*1/2)，通常忽略常数项，得算法时间为O(n^2)
