二分查找
选择排序
递归
快速排序
广度优先搜索
狄克斯特拉算法
贪婪算法
二分查找
def binary_search(lst,item): low = 0 high = len(lst)-1 while low <= high: mid = (high+low)//2 if item == lst[mid]: return mid if item < lst[mid]: high = mid-1 if item > lst[mid]: low = mid + 1 return None my_list = [1,3,5,7,9] print(binary_search(my_list,5))
选择排序
def findsmallest(arr): smallest = arr[0] smallest_index = 0 for i in range(1,len(arr)): if arr[i] < smallest: smallest = arr[i] smallest_index = i return smallest_index def selection_Sort(arr): new_arr = [] for i in range(len(arr)): new_arr.append(arr.pop(findsmallest(arr))) # 注意pop的对象是索引 return new_arr arr = [3,1,5,2,9,1,1,0] print(selection_Sort(arr))
递归
# 倒计时 def countdown(n): print(n) if n < 1: return countdown(n-1) # 求和 def sum_1(arr): if arr == []: return 0 return arr.pop(0) + sum_1(arr) def sum_2(arr): if arr == []: return 0 return arr[0] + sum_2(arr[1:]) arr = [1,2,3,4,5] print(sum_1(arr)) # 阶乘 def fact(n): if n == 1: return 1 return n * fact(n - 1) # 计算元素个数 def count_arr(arr): if arr == []: return 0 return 1 + count_arr(arr[1:])
快速排序
def quick_sort(arr): if len(arr) < 2: return arr else: pivot = arr[0] less = [i for i in arr[1:] if i <= pivot] greater = [i for i in arr[1:] if i > pivot] return quick_sort(less) + pivot + quick_sort(greater)
广度优先搜索
# 使用队列这种数据结构 from collections import deque # 定义图 graph = { 'you': ['alice', 'bob', 'claire'], 'bob': ['anuj', 'peggy'], 'alice': ['peggy'], 'claire': ['thom', 'jonny'], 'anuj': [], 'peggy': [], 'thom': [], 'jonny': [] } # 判断是否是芒果销售商 def person_is_seller(name): return name[-1] == "m" # 广度优先搜索 def search(name): # 实例化队列 search_deque = deque() # 将某人的一度关系网加入到队列中 search_deque += graph[name] # 初始化已检查过的人 searched = [] # 队列中存在元素时就一直搜索 while search_deque: # 从列队中弹出第一个人，并检查 person = search_deque.popleft() # 此人不在已检查过的列表中 if person not in searched: # 检查是否是销售商 if person_is_seller(person): print("%s is mango_seller" % person) return True else: # 如果不是就将此人的一度关系网加入到队列中 search_deque += graph[person] searched.append(person) return False search("you")
狄克斯特拉算法
# 创建图的散列表 graph = { "start":{"a":6,"b":2}, "a":{"fin":1}, "b":{"a":3,"fin":5}, "fin":{} } # 创建开销的散列表 costs = { "a":6, "b":2, "fin":float("inf") } # 创建存储父节点的散列表 parents = { "a":"start", "b":"start", "fin": None } # 记录处理过的节点 processed = [] # 在未处理的节点中寻找最小开销节点 def find_lowest_cost_node(costs): lowest_cost = float("inf") lowest_cost_node = None for node in costs: cost = costs[node] if cost < lowest_cost and node not in processed: lowest_cost = cost lowest_cost_node = node return lowest_cost_node # 1、拿到起点的一度关系中的最小开销节点 node = find_lowest_cost_node(costs) # 2、获取该节点的开销和邻居 while node is not None: cost = costs[node] neighbors = graph[node] # 3、遍历邻居 for n in neighbors.keys(): # 计算该节点到邻居的开销+起点到该节点的开销，与起点直接到改点的开销比较 new_cost = cost + neighbors[n] # 如果前者开销较小则更新改邻居节点的父节点，并更新起点到该邻居节点的开销 if new_cost < costs[n]: parents[n] = node costs[n] = new_cost # 4、将当前节点标记为处理过 processed.append(node) # 5、找出接下来要处理的节点并循环 node = find_lowest_cost_node(costs) print(processed) print(costs) print(parents)
贪婪算法
# 目标：选择尽可能少的电台覆盖尽可能多的州 # 方法：第一步，选择覆盖州最多的电台 # 方法：第二步，选择覆盖最多“未覆盖的州（上一步剩下的州）”的电台 # 方法：第三步，重复第二步，直到覆盖所有的州 # 需要覆盖的州 states_needed = set(["mt", "wa", "or", "id", "nv", "ut","ca", "az"]) # 电台清单 stations = { "kone" : set(["id", "nv", "ut"]), "ktwo" : set(["wa", "id", "mt"]), "kthree" : set(["or", "nv", "ca"]), "kfour" : set(["nv", "ut"]), "kfive" : set(["ca", "az"]) } # 该集合存储最终选择的电台 final_stations = set() # 只要需要覆盖的州不为空就一直循环 while states_needed: best_station = None states_covered = set() # 从电台清单中找出覆盖未覆盖州最多的电台 for station,states in stations.items(): covered = states_needed & states if len(covered) > len(states_covered): best_station = station states_covered = covered # 每次确定一个最佳的电台就将其覆盖的州从总集合中减去 states_needed -= states_covered # 没确定一个最佳电台就存在最终的电台集合中 final_stations.add(best_station) print(final_stations)