这两天阅读了算法图解的第一章和第二章，刚好可以记录一下。
1.二分法
说明：二分法是对已排序的序列进行查找某数的一种算法。要查找一个数在序列的某个位置，也许可以采用从头到尾一个一个地找，如果一共有n个数，那么最坏可能要查找n次。但使用二分法，每次查找就能把范围缩小一半，n可以对半多少次？log2n次！也就是说随着n的增加，二分法的速度要快很多。
二分法：
取序列中间的数与给定的值进行比较，若大于，则取小的那一半序列；反之，取大的那一半序列。再取新序列的中间值与给定数比较，进行同样的判断。直到取到最后一个数。
因为目标值需要对序列中间值进行比较，所以需要取中间位置mid；然后每次比较后都需要更新序列的范围，这个范围可以用high与low进行确定，比较后根据情况把mid值给high或者low，最后返回下标。
def binary_search(array, item):
"""
二分法：算法复杂度log2n
input: array一个排序好的序列；item:待查找的值
return：排序后值所在的下标
"""
low = 0
high = len(array) - 1
#边界条件
while low <= high:
mid = (low + high)//2
if array[mid] == item:
return mid
elif array[mid] < item:
low = mid + 1
else:
high = mid - 1
return None
2.选择排序
说明：每次选择序列中的最小值，将其排到最左边；然后选择剩下位置的最小值，再将其排到剩下位置最左边，直到最后一个位置排好。第一次查询n，第二次查询n-1...第n次1，因此需要查询n(n+1)/2≈n^2
方法1：书中定义了一个查找序列最小值的函数，然后定义了一个空数组来依次接收最小值。
def findSmallest(arr):
"""
找数组中的最小值的index
"""
smallest = arr[0]
smallest_ind = 0
for i in range(len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_ind = i
return smallest_ind
#使用额外数组
def selectSort1(arr):
"""
选择排序：将元素按从小到大排序
input: 一个数组
return: 由小到大排序好的数组
使用额外数组
"""
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest)) #arr要将最小的去掉，而newArr要将最小的加入
return newArr
根据上面的两段函数，可以把代码进行更改，实现不需要额外的空间。
方法2：每次查找序列的最小值，将最小值与最左边的值进行交换。因为序列每次排序好一个后就需要更新，因此使用两个循环：小循环找到最小值，大循环确定序列的起始值和进行交换的位置。交换两个值，需要一个中间变量用于接收，不然里面的值会被刷新（a<->b: a->c, b->a, c->b）。
def selectSort2(arr):
"""
选择排序：将元素按从小到大排序
input: 一个数组
return: 由小到大排序好的数组
不使用额外数组
"""
#设定两个指针，快指针进行遍历-找最小值，慢指针确定起始点
L = len(arr)
for i in range(L):
smallest = arr[i]
smallest_ind = i
for j in range(i, L):
if arr[j] < smallest:
smallest = arr[j]
smallest_ind = j
arr[smallest_ind] = arr[i]
arr[i] = smallest
return arr
