# 《算法图解》代码实现和改进

xiaoxiao2021-02-28  12

# 《算法图解》代码实现和改进

## 二分查找

def bin_search(list,item): low = 0 high = len(list) - 1 while low<=high: mid = (low+high)//2 #得到中间值 guess = list[mid] if guess==item: return mid elif guess>item: high = mid-1 else: low = mid+1 return None func = lambda x:x%2!=0 my_list = list(filter(func,range(0,10))) print(my_list) print(bin_search(my_list,2)) print(bin_search(my_list,5)) [1, 3, 5, 7, 9] None 2

## 数组和链表

#### 选择排序

def findSmall(arr):#找到最小 small = arr[0] small_index = 0 for i in range(1,len(arr)): if arr[i]<small: small = arr[i] small_index = i return (small_index,small) def selectionSelect(arr):#选择排序,升序 newArr = [] for i in range(len(arr)): small_index = findSmall(arr)[0] newArr.append(arr.pop(small_index)) return newArr print(selectionSelect([i for i in range(10,0,-1)])) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

## 递归

#### 盒子查找

##### 迭代写法
def lookForKey(mainBox): pile = mainBox.makePileToLook() while len(pile): box = pile.grabBox() for item in box: if item.isBox(): pile.append(item) elif item.isKey(): print("found the key!")
##### 递归写法
def lookForKey(box): for item in box: if item.isBox(): lookForKey(item) elif item.isKey(): print('Found the key at ',item)

## 基线条件和递归条件

def countdown(i): print(i) if i-1: countdown(i-1) else : return countdown(5) 5 4 3 2 1

## 快速排序

#### 分而治之

def Sum(arr): if len(arr): return arr[0] + Sum(arr[1:]) else: return 0 Sum([i for i in range(1,101)]) 5050

#### 找到最大值

''' 错误的写法，out of range def getMax(arr,index=0): if len(arr)>1: new_index = index + 1 print(new_index,len(arr)) return arr[index] if arr[index]>getMax(arr[new_index:],new_index) else getMax(arr[new_index:],new_index) else: return arr[index] ''' def getMax(arr): if arr and len(arr)>1: return arr[0] if arr[0] > getMax(arr[1:]) else getMax(arr[1:]) else: return arr[0] import random List = [i for i in range(6)] random.shuffle(List) print(List) getMax(List) [1, 4, 5, 2, 3, 0] 5

#### 快速排序

def quickSort(arr): if len(arr)<2: return arr #基线条件，为空或者只含有一个元素的数组 else: pivot = arr[0] # 递归条件，这里可以随机选取的 small= [i for i in arr[1:] if i<=pivot] #小于基准值组成的子数组 big = [i for i in arr[1:] if i>pivot] return quickSort(small) +[pivot] + quickSort(big) print(quickSort([10,5,3])) [3, 5, 10]

#### 快速排序改进（个人代码，可能有bug）

from random import randrange def quickSort(arr): if len(arr)<2: return arr else: flag = 0 for i in range(0,len(arr)-1): if arr[i]>arr[i+1]: flag = 1 break if flag: index = randrange(0,len(arr)) pivot = arr[index] small = [arr[i] for i in range(0,len(arr)) if i!=index and arr[i]<=pivot] big = [arr[i] for i in range(0,len(arr)) if i!=index and arr[i]>pivot] return quickSort(small)+[pivot]+quickSort(big) else: return arr print(quickSort([10,5,3,-5])) [-5, 3, 5, 10]

## 散列表

### python里面实现方式是字典

##### DNS实现
dns = {} dns['google.com'] = '74.125.239.133' dns['scribd.com'] = '23.235.47.175' site = input('>>> ') print(site,dns.get(site)) >>> google.com google.com 74.125.239.133
##### 投票
voted = {} def check_voter(name): if voted.get(name): print('已经投过票') else: voted[name] = True print('可以投票') check_voter('Tom') check_voter('Vic') check_voter('Tom') 可以投票 可以投票 已经投过票
##### 用户缓存
cache = {} def get_page(url): if cache.get(url): return chache[url]#返回缓存数据 else: data = get_data_from_server(url)#默认配置 cache[url] = data return data

## 广度优先搜索(BFS)

### 实现图

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'] = []

### 队列

from collections import deque type(search_queue) collections.deque def person_is_seller(name): return name[-1] == 'm' def search(name): search_queue = deque()#创建对列 global graph search_queue += graph[name]#从谁开始搜索 searched = []#已经搜索，防止无限循环 while search_queue:#只要队列里有人 person = search_queue.popleft()#取出一人 if person not in searched: if person_is_seller(person): print(person+' is a mango seller') return True else: search_queue+=graph[person] searched.append(person) return False search('you') thom is a mango seller True

## 贪婪算法(不一定是最优解,非常接近)

### 集合操作

fruits = set(['avocado','tomato','banana']) vegetables = set(['beets','carrots','tomato']) print('|:并集\n\t',fruits | vegetables) print('&:交集\n\t',fruits & vegetables) print('-:差集\n\t',fruits - vegetables) |:并集 {'tomato', 'avocado', 'beets', 'carrots', 'banana'} &:交集 {'tomato'} -:差集 {'avocado', 'banana'}

### 模糊算法--集合覆盖问题

states_needed = set(['mt','wa','or','id','nv','ut','ca','az']) stations = {} stations['kone'] = set(['id','nv','ut']) stations['ktwo'] = set(['wa','id','mt']) stations['kthree'] = set(['or','nv','ca']) stations['kfour'] = set(['nv','ut']) stations['kfive'] = set(['ca','az']) final_stations = set()#最终电台 while states_needed: best_station = None#存放覆盖区域最多的电台 states_covered = set() for station,states_for_station in stations.items(): covered = states_needed & states_for_station if len(covered)>len(states_covered): best_station = station states_covered = covered states_needed -= states_covered final_stations.add(best_station) del stations[best_station]#用过的删除 print(final_stations) {'kfive', 'ktwo', 'kone', 'kthree'}