Python 图解算法 递归快速排序散列表广度优先搜索

图解算法 递归/快速排序/散列表/广度优先搜索 1.递归

每个递归函数都有两个条件：基线条件和递归条件

简单例子：实现sum函数

# 1.实现sum函数
def sumNumber(arr):
    if arr==[]:
        return 0 
    else:
        print(arr.pop())
        return arr.pop()+sumNumber(arr)

print(sumNumber([2,5,7,10]))

2.快速排序 O(nlogn)

分而治之（divide and conquer, D&C）是著名的递归式问题解决方法
快速排序-重要的D&C算法

# 2.快速排序 O(nlogn)
def quicksort(array):
    if len(array)<2: # 递归的基线条件：数组为空或者只包含一个元素，这时的数组是有序的
        return array
    else:
        pivot=array[0] # 选择一个数作为基准值（pivot）
        less=[i for i in array[1:] if i <= pivot] # 找出比基准值小的数组 
        # array[1:] 除去基准值以外的数组
        greater=[i for i in array[1:] if i > pivot] #找出比基准值大的数组
        return quicksort(less)+[pivot]+quicksort(greater)

print (quicksort([5,6,10,2,3]))

3.散列表

# 散列表hash table
# 作用：
# 1.查找
phone_book=dict()
phone_book["jenny"] = 8675309
phone_book["emergency"] = 911
# 2.防止重复
voted = {}
def check_voter(name):
    if voted.get(name):
        print("kick them out!")
    else:
        voted[name] = True
        print("let them vote!")
# 3.用作缓存(浏览器缓存原理)
cache = {}
def get_page(url):
    if cache.get(url):
        return cache[url] # 返回缓存的数据
    else:
        data = get_data_from_server(url)
        cache[url] = data # 先将数据保存到缓存中
        return data

4.广度优先搜索

图： 一种新的数据结构
广度优先搜索(breadth-first search BFS)：一种图算法
知识点①：BFS可以回答的问题：
1.A TO B 有路径吗？
2.A TO B 最短路径？
知识点②：
队列：先进先出
栈：后进先出
知识点③：BFS运行时间
O（人数+边数）-O（V+E）

# !例：寻找芒果销售商
from collections import deque
#建立每个人之间的关系
graph = {} 
graph["you"] = ["alice", "bob", "claire"] 
graph["bob"] = ["anuj", "peggy"] 
graph["alice"] = ["peggy"] 
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = [] 
graph["peggy"] = [] 
graph["thom"] = [] 
graph["jonny"] = [] 

def person_is_seller(name):#判断一个人是不是芒果销售商
    return 'mango' in name

def search(name):
    search_queue=deque() #创建一个队列
    search_queue +=graph['you'] #将你的邻居加入到搜索队列中
    searched=[] #用于保存检查过的人 不然会一直循环


    while search_queue: #如果队列不为空
        person=search_queue.popleft() #取出其中的第一个人
        #检查他是不是芒果销售商
        if person_is_seller(person):
            print('Mango seller is:'+person)
            return True
        else:
            #把朋友的朋友加入队列
            search_queue+=graph[person] 
            searched.append(person)
    print('No one find!')
    return False

search('you')