二分查找
大O表示法
选择排序
递归
快速排序，分而治之（D&C）
散列表——字典
广度优先搜索——BFS
Dijkstra算法
贪婪算法
1 # 要求list是有序表，num是要查找的数字 2 # 二分查找貌似只能查找数值表 3 def binary_search(list, num): 4 low = 0 5 high = len(list) - 1 # 因为python数组（列表）是从0开始索引的 6 7 while low <= high: 8 mid = (low + high) 9 guess = list[mid] 10 if guess == num: 11 return "found it is " + str(mid) 12 if guess > num: 13 high = mid - 1 14 else: 15 low = mid + 1 16 return "not found" 17 18 # python数组不同于matlab数组，python中间要用逗号隔开，而matlab不用 19 my_list = [1, 3, 5, 7, 9, 11, 13] 20 print(binary_search(my_list, 6)) 21 print(binary_search(my_list, 9))
1 寻找数组中的最小值的索引 2 def find_smallest_index(arr): 3 smallest = arr[0] 4 smallest_index = 0; 5 # python中检查数组长度的函数是len，而matlab中是length 6 for i in range(1, len(arr)): 7 if arr[i] < smallest: 8 smallest = arr[i] 9 smallest_index = i 10 return smallest_index 11 12 # 对数组进行排序 13 def selection_insort(arr): 14 # create new array 15 new_arr = [] 16 for i in range(len(arr)): 17 smallest_index = find_smallest_index(arr) 18 # array.pop()只能根据索引值弹出元素，so pop()应传入索引值 19 new_arr.append(arr.pop(smallest_index)) 20 return new_arr 21 22 mess_arr = [3, 1, 9, 2, 5, 4] 23 print("This is uninsort array: " + str(mess_arr)) 24 insorted_arr = selection_insort(mess_arr) 25 print("This is insorted array: " + str(insorted_arr))
1 # 一个计算数学阶乘的递归调用 2 def func(x): 3 if x == 1: 4 return 1 5 else: 6 return x * func(x-1) 7 8 print(func(3)) 9 10 11 #一个计算数组和的递归调用 12 def func(arr): 13 if arr == []: 14 return 0 15 else: 16 # 这里不能用arr[0] + func()因为基线条件是arr==[]当arr 17 # 只有一个元素时python会将arr变为一个int数值，而不会是数组 18 return arr.pop() + func(arr) 19 20 arr = [2, 3, 4] 21 print(func(arr))
1 # 快速排序——by myself 2 def quickly_sort(arr): 3 # 两个基线条件 4 if len(arr) < 2: 5 return arr 6 # 直接选取数组元素第一个当作基准值——递归条件 7 reference_value = arr[0] 8 larger_arr = [] 9 smaller_arr = [] 10 for i in range(1,len(arr)): 11 if arr[i] > reference_value: 12 larger_arr.append(arr[i]) 13 # arr.pop(i) 14 else: 15 smaller_arr.append(arr[i]) 16 # arr.pop(i) 17 return quickly_sort(smaller_arr) + [reference_value] + quickly_sort(larger_arr) 18 19 mess_arr = [3, 1, 9, 2, 5, 4] 20 print("This is uninsort array: " + str(mess_arr)) 21 insorted_arr = quickly_sort(mess_arr) 22 print("This is insorted array: " + str(insorted_arr))
1 # 快速排序——by others 2 def quickly_sort(arr): 3 # 基线条件 4 if len(arr) < 2: 5 return arr 6 else: 7 # 选取基准值——递归条件 8 pivot = arr[0] 9 10 # 简洁明了选出较大数组与较小数组 11 larger = [i for i in arr[1:] if i > pivot] 12 smaller = [i for i in arr[1:] if i <= pivot] 13 # 递归调用 14 return quickly_sort(smaller) + [pivot] + quickly_sort(larger) 15 16 mess_arr = [3, 1, 9, 2, 5, 4] 17 print("This is uninsort array: " + str(mess_arr)) 18 insorted_arr = quickly_sort(mess_arr) 19 print("This is insorted array: " + str(insorted_arr))
1 # 散列表——字典 2 # 创建字典的两种方案 3 price_list = dict() 4 price_list = {} 5 6 7 # 添加数据 8 price_list["apple"] = 0.67 9 price_list["milk"] = 1.49 10 price_list["bread"] = 0.49 11 12 print(price_list) 13 print(price_list.keys()) 14 print(price_list.values()) 15 print(price_list.items()) 16 17 # 判断是否在散列表中 18 flag = price_list.get("apple") 19 print(flag) 20 # 不同大小写诗不同与阿奴 21 flag = price_list.get("Apple") 22 print(flag) 23 flag = price_list.get("banana") 24 print(flag)
1 # 广度优先搜索示例 2 from collections import deque 3 4 # 创建一个关系图（散列表） 5 graph = {} 6 # 单引号与双引号基本无使用上的区别，但是三引号可实现跨行输出 7 graph["you"] = ["alice", ‘bob‘, "claire"] 8 graph["alice"] = [‘peggy‘] 9 graph["bob"] = ["anuj", ‘peggy‘] 10 graph[‘claire‘] = ["thom", ‘jonny‘] 11 graph["peggy"] = [] 12 graph["anuj"] = [] 13 graph["thom"] = [] 14 graph["jonny"] = [] 15 16 17 search_queue = deque() 18 search_queue += graph["you"] 19 20 # 判断是否为经销商 21 def person_is_seller(name): 22 return (name[-1] == ‘o‘) 23 24 def search(search_queue): 25 searched = [] 26 while search_queue: 27 28 person = search_queue.popleft() #取出队列左边第一个元素 29 # 检查后不再检查 30 if person not in searched: 31 if person_is_seller(person): 32 print(person + " is a mago seller !") 33 return True 34 else: 35 # 把TA的朋友加入搜索队列 36 search_queue += graph[person] 37 searched.append(person) 38 print("Can‘t find mago seller in your friends") 39 return False 40 search(search_queue)
1 # Dijkstra算法 2 3 # 寻找lowest_cost_node 4 def find_lowest_cost_node(costs): 5 lowest_cost = float("inf") 6 lowest_cost_node = None 7 for node in costs: 8 cost = costs[node] 9 if cost < lowest_cost and node not in processed: 10 lowest_cost = cost 11 lowest_cost_node = node 12 return lowest_cost_node 13 14 15 # Create a graph 16 graph = {} 17 graph[‘start‘] = {} 18 graph[‘start‘][‘a‘] = 6 19 graph[‘start‘][‘b‘] = 2 20 graph[‘a‘] = {} 21 graph[‘a‘][‘fin‘] = 1 22 graph[‘b‘] = {} 23 graph[‘b‘][‘fin‘] = 5 24 graph[‘b‘][‘a‘] = 3 25 graph[‘fin‘] = {} 26 27 28 # create a cost dict 29 infinity = float(‘inf‘) 30 costs = {} 31 costs[‘a‘] = 6 32 costs[‘b‘] = 2 33 costs[‘fin‘] = infinity 34 35 # creata a parent dict 36 parents = {} 37 parents[‘a‘] = "start" 38 parents[‘b‘] = "start" 39 parents[‘fin‘] = None 40 41 42 # record processed nodes 43 processed = [] 44 45 46 node = find_lowest_cost_node(costs) 47 while node is not None: 48 cost = costs[node] 49 neighbors = graph[node] 50 for n in neighbors.keys(): 51 new_cost = cost + neighbors[n] 52 if costs[n] > new_cost: 53 costs[n] = new_cost 54 parents[n] = node 55 processed.append(node) 56 node = find_lowest_cost_node(costs) 57 58 route = [‘fin‘] 59 node = parents[‘fin‘] 60 route.append(node) 61 node = parents[node] 62 route.append(node) 63 node = parents[node] 64 route.append(node) 65 66 67 print(route)
原文：https://www.cnblogs.com/morvan/p/11940236.html
