算法
二分查找
def binary_search(list,item):
low =0
high = len(list)-1
while(low<=high):
mid = (low + high)//2
guess = list[mid]
if guess == item:
return mid
if guess < item:
high = mid-1
else:
low = mid+1
return None
l = [2,4,6,8,10]
x = binary_search(l,6)
if x==None:
print("列表中无此数")
else:
print('此数在列表中的第%s位'%x)
运行结果
此数在列表中的第2位
选择排序
#选择排序
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 selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
return newArr
l = [6,8,7,9,0,1,3,2,4,5]
print(selectionSort(l))
运行结果
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
快速排序
def quicksort(arr):
if len(arr)<2:
return arr
left = []
right =[]
pivot = arr[0]
for i in range(1,len(arr)):
if arr[i]<pivot:
left.append(arr[i])
else:
right.append(arr[i])
return quicksort(left) + [pivot] +quicksort(right)
a = quicksort([6,8,7,9,0,1,3,2,4,5])
print(a)
def quicksort(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 quicksort(less) + [pivot] + quicksort(greater)
运行结果
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
广度优先搜索
#实现图
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
search_queue = deque() #创建一个队列
search_queue +=graph["you"] #将你的邻居都加入到这个搜索队列中
#广度优先搜索
def bfsearch(name):
search_queue = deque()
search_queue += graph[name]
searched = [] #该列表用于记录检查过的人
while search_queue:
person = search_queue.popleft()
if not person 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
def person_is_seller(name):
return name[-1] == 'm'
bfsearch("you")
运行结果
thom is a mango seller!
深度优先搜索
#图
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"] = []
#栈类
class SStack(): #基于顺序表技术实现的栈类
def __init__(self): #用list对象_elems存储栈中元素
self._elems = []
def is_empty(self):
return self._elems == []
def top(self):
if self._elems == []:
print("栈为空")
return self._elems[-1]
def push(self,elem):
self._elems.append(elem)
def pop(self):
if self._elems == []:
print("栈为空")
return self._elems.pop()
st1 = SStack()
#深度优先搜索
def person_is_seller(name):
return name[-1] == 'm'
def dfsearch(name):
st = SStack()
searched = []
if graph[name]!=[]:
for i in graph[name]:
st.push(i)
while not st.is_empty():
person = st.pop()
if not person in searched:
if person_is_seller(person):
print(person + " is a mango seller!")
return True
searched.append(person)
if graph[person]!=[]:
for j in graph[person]:
st.push(j)
return False
dfsearch("you")
#栈实现深度优先遍历
def dfsearch1(name):
st = SStack()
searched = []
print(name)
if graph[name]!=[]:
for i in graph[name]:
st.push(i)
while not st.is_empty():
person = st.pop()
if not person in searched:
print(person)
searched.append(person)
if graph[person]!=[]:
for j in graph[person]:
st.push(j)
dfsearch1("you")
运行结果
thom is a mango seller!
you
claire
jonny
thom
bob
peggy
anuj
alice
狄克斯特拉算法
#狄克斯特拉算法
#表示整个图的散列表
graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["fin"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5
graph["fin"] = {}
#创建开销表
infinity = float('inf')
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
#创建存储父节点的散列表
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["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
node = find_lowest_cost_node(costs) #在未处理的节点中找出开销最小的节点
while node is not None:
print(node)
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys(): #遍历当前节点的所有邻居
new_cost = cost + neighbors[n]
if costs[n]>new_cost: #如果经当前节点千万该邻居更近
costs[n]=new_cost #就更新该邻居的开销
parents[n]=node #同时将该邻居的父节点设置为当前节点
processed.append(node) #将当前节点标记为处理过
node = find_lowest_cost_node(costs) #找出接下来要处理的节点，并循环
运行结果
b
a
fin
贪婪算法
#创建一个列表，其中包含要覆盖的州
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)
print(final_stations)
运行结果
{'kfive', 'kthree', 'ktwo', 'kone'}
