# 咸糖记录编程的地方

/

## 算法图解4.5-7章笔记(qsort,Dijkstra)

### qsort 时间复杂度

• 最糟糕(头)
1. 以头为基准,需要涉及整个列表
2. 因为要遍历两边的数组,而且O(n)不受常量影响
• 最优(中间)
1. 以中间为基准(类似二分log n)
2. 每层O(n)
最佳的就是平均的情况
TODO: 随机的选择用作基准的元素
``````array = [5,7,2,4,3,1,8,6]
from random import randint
def qsort(array):
if len(array)<=1:
return array
ran=randint(0,len(array)-1)

mid = array[ran]
array.pop(ran)
smaller = [ i for i in array   if i<=mid]
bigger = [i for i in array  if i>mid ]
return  qsort(smaller) + [mid] +qsort(bigger)

print(qsort(array))
``````

DNS 解析

### 广度优先遍历

``````from collections import deque

graph = {}
graph['you'] = ["alice","bob","claire"]
graph['bob'] = ["anuj","peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom","jooy"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

def person_is_seller(name):
return name[-1] == 'm'
# deque

def find():
search_queue = deque()
search_queue += graph["you"]
while search_queue:
person = search_queue.popleft()
if person_is_seller(person):
print(person +"is seller")
return True
else:
search_queue +=graph[person]
return False
find()
``````

``````from collections import deque
def person_is_seller(name):
return name[-1] == 'm'
graph = {}
graph['you'] = ["alice","bob","claire"]
graph['bob'] = ["anuj","peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom","jooy"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []
search_queue = deque()

def find2(search_queue):
if search_queue:
person = search_queue.popleft()
if person_is_seller(person):
print(person +"is seller")
return True
else:
search_queue +=graph[person]
return find2(search_queue)
else:
return None

search_queue += graph["you"]
print(find2(search_queue))
``````
• 广度优先遍历是找到是否A-B的
• 有就可以找到最短路径
• 有向图可以指定方向
• 无向图关系双向
• 按照顺序放入队列就可以找到最短路径,检查过的人需要放入去重列表

### 迪杰斯特拉算法

``````graph = {}
graph['start'] = {}
graph['start']['a'] = 5
graph['start']['b'] = 0
graph['a'] = {}
graph['a']['c'] = 15
graph['a']['d'] = 20
graph['b'] = {}
graph['b']['c'] = 30
graph['b']['d'] = 25
graph['c'] = {}
graph['c']['fin'] = 20
graph['d'] = {}
graph['d']['fin'] = 10
graph['fin'] = {}
costs = {}

costs['a'] = 5
costs['b'] = 0
costs['c'] = float("inf")
costs['d'] = float("inf")
costs['fin'] = float("inf")
parents = {}
parents['a'] = 'start'
parents['b'] = 'start'
parents['c'] = 'start'
parents['d'] = 'start'
parents['fin'] = None
processed = []
def find_lowst(costs):
low_cost = float("inf")
low_cost_node = None
for node in costs:
cost = costs[node]
if cost < low_cost and node not in processed:
low_cost = cost
low_cost_node = node
return low_cost_node

node = find_lowst(costs)
while node is not  None:
cost = costs[node]
friends = graph[node]
for friend in friends.keys():
new_cost = friends[friend]+cost
# if new_cost <
if new_cost < costs[friend]:
costs[friend] = new_cost
parents[friend] = node
processed.append(node)
node = find_lowst(costs)
print(costs)
``````

``````graph = {}
graph['start'] = {}
graph['start']['a'] = 5
graph['start']['b'] = 0
graph['a'] = {}
graph['a']['c'] = 15
graph['a']['d'] = 20
graph['b'] = {}
graph['b']['c'] = 30
graph['b']['d'] = 25
graph['c'] = {}
graph['c']['fin'] = 20
graph['d'] = {}
graph['d']['fin'] = 10
graph['fin'] = {}
def get_costs_parent(graph):
costs = {}
parents = {}
for node in graph.keys():
if node in graph['start'].keys():
costs[node] = graph['start'][node]
parents[node] = 'start'
else:
costs[node] = float('inf')
parents[node] = None
return costs,parents
costs ,parents= get_costs_parent(graph)

processed = []
def find_lowst(costs):
low_cost = float("inf")
low_cost_node = None
for node in costs:
cost = costs[node]
if cost < low_cost and node not in processed:
low_cost = cost
low_cost_node = node
return low_cost_node
node = find_lowst(costs)
while node is not  None:
cost = costs[node]
friends = graph[node]
for friend in friends.keys():
new_cost = friends[friend]+cost
# if new_cost <
if new_cost < costs[friend]:
costs[friend] = new_cost
parents[friend] = node
processed.append(node)
node = find_lowst(costs)
print(costs['fin'])
``````
``````graph = {}
graph['start'] = {}
graph['start']['a'] = 5
graph['start']['b'] = 0
graph['a'] = {}
graph['a']['c'] = 15
graph['a']['d'] = 20
graph['b'] = {}
graph['b']['c'] = 30
graph['b']['d'] = 25
graph['c'] = {}
graph['c']['fin'] = 20
graph['d'] = {}
graph['d']['fin'] = 10
graph['fin'] = {}
def get_costs_parent(graph):
costs = {}
parents = {}
for node in graph.keys():
if node in graph['start'].keys():
costs[node] = graph['start'][node]
parents[node] = 'start'
else:
costs[node] = float('inf')
parents[node] = None
return costs,parents
costs ,parents= get_costs_parent(graph)

def find_lowst(costs):
low_cost = float("inf")
low_cost_node = None
for node in costs:
cost = costs[node]
if cost < low_cost and node not in processed:
low_cost = cost
low_cost_node = node
return low_cost_node
def find_short_path(costs,processed,parents):
node = find_lowst(costs)
if node is not None:
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys():
new_cost = neighbors[n] + cost
if new_cost < costs[n]:
costs[n] = new_cost
parents[n] = node
processed.append(node)
return find_short_path(costs,processed,parents)

else:
return costs['fin']
processed = []

fastst = find_short_path(costs,processed,parents)
``````

* 基准条件:找到的最小节点为空
* 递归条件:还有节点没有处理

####主要思路:
1. 找到一个节点然后取找他的所有相邻节点
2. 将相邻节点到本节点的距离与本节点到起点的距离相加
3. 判断是否比相邻结点原来的距离短
4. 如果更短直接更新,并且加入去重列表
5. 如何取找一个节点:我们选取的是最小的节点,如果这个节点不在去重队列