###算法图解读书笔记1

quick sort

概念 先找一个pivot, 最后的结果为 qsort([less than pivot]) + [pivot] + qsort([more than pivot])

1
2
3
4
5
6
7
def qsort(list):
if len(list) < 2:
return list
pivot = list.pop()
left = filter(lambda x: x <= pivot, list)
right = filter(lambda x: x > pivot, list)
return qsort(left) + [pivot] + qsort(right)

merge sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#The merge method takes in the two subarrays and creates a output array
def merge(left, right):
result = []
i , j = 0 , 0
while i < len (left) and j < len (right): # iterate through both arrays and arrange the elements in sorted order
if left[i] <= right [j]:
result.append(left[i])
i+=1
else:
result.append(right[j])
j+=1

#The loop may break before all elements are copied hence append the remaining elements
result += left[i:]
result += right[j:]
return result


#The mergesort method to split the arrays into smaller subarrays
def mergesort(lst):
if len(lst) <= 1:
return lst
middle = int(len(lst) / 2)
left = mergesort(lst[:middle])
right = mergesort(lst[middle:])
return merge(left, right)


if __name__ == '__main__':
print mergesort([3, 4, 8, 0, 6, 7, 4, 2, 1, 9, 4, 5])

散列表(hash table)

  • 将key映射成数字以加快查找
  • 数据较多的时候有可能会产生冲突,这个时候就在冲突的位置生成一个链表
  • 散列函数很重要,最好把数据均匀的分配到系统中,防止出现全部映射到一个位置的情况

BFS

  • 解决到x的最短路径是什么等问题
  • 因为解决的是最短路径,所以需要便利第一层,如果第一层没有到结果,然后第二层,所以需要queue作为数据结构

实例应用

  • 国际象棋,多少步可以获胜
  • 拼写检查器,编辑多少个地方可以将错的词改成正确的词如READED改为READER需要编辑一个地方
  • 人际关系找到最近的医生

邻接矩阵(Adjacency Matrix)

http://www.cnblogs.com/zhangming-blog/p/5412085.html
利用这种表示方法也可以表示加权路径

floyd算法(求图两个点的最短距离)

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/floyd.html

1
2
3
4
5
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>
e[i][k]+e[k][j])

e[i][j]=e[i][k]+e[k][j];

基础思想是,设想会经过第一个点,更新各个点最短路径,之后设想会经过第二个点,更新最短路径。直到比对完所有的点,然后更新了全部的路径,最后求出某两个点的最短长度