二分查找
- Ｏ(log2*n)
- 有序的元素列表
import math
#導(dǎo)入math
#math.ceil（ˇ?ˇ） 向上取整
#math.floor 向下取整
#math.round 四舍五入
#均返回ｆｌｏａｔ型
def binary_search(arr,key):
head=0
tail=len(arr)
middle=int(math.ceil((head+tail)/2))
while tail>head:
if arr[middle]==key:
print "got it at "+str(middle)
return
elif arr[middle]<key:
head=middle+1
elif arr[middle]>key:
tail=middle-1
middle=int(math.ceil((head+tail)/2))
arr=[1,2,3,4,5,6,7,8,9]
binary_search(arr,6)
－－－－－output－－－－－
got it at 5
選擇排序
- O(n^2)
def findSmallest(arr):
smallest = arr[0]
smallest_index = 0
for i in range(1,len(arr)):
if smallest > arr[i]:
smallest = arr[i]
smallest_index = i
return smallest_index
def select_sort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
return newArr
快速排序
def quicksort(arr):
if len(arr)<2:
return arr
else:
pivot = arr[0]
less =[i for i in arr if i<pivot]
geter = [i for i in arr if i>pivot]
return quicksort(less)+[pivot]+quicksort(geter)
print quicksort([2,1,3,4,5,6])
廣度優(yōu)先查找
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(person):
return person[-1] == 'm'
def search(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
search('you')
迪克斯特拉算法
graph = {}
graph["start"] = {}
graph["start"]["a"] = 5
graph["start"]["b"] = 2
graph["a"] ={}
graph["a"]["c"] = 4
graph["a"]["d"] = 2
graph["b"] = {}
graph["b"]["a"] = 8
graph["b"]["d"] = 7
graph["c"] = {}
graph["c"]["fin"] = 3
graph["c"]["d"] = 6
graph["d"] = {}
graph["d"]["fin"] = 1
graph["fin"] = {}
infinity = float("inf")
costs = {}
costs["a"] = 5
costs["b"] = 2
costs["c"] = 9
costs["d"] = 9
costs["fin"] = infinity
partents = {}
partents["a"]="start"
partents["b"] = "start"
partents["c"] = "a"
partents["d"] = "b"
partents["fin"] = None
processed = []
def fine_lowest_cost_node(costs):
lowest_cost = infinity
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 = fine_lowest_cost_node(costs)
while node is not None:
cost = costs[node]
neightbors = graph[node]
for n in neightbors.keys():
new_cost = cost+neightbors[n]
if costs[n] > new_cost:
costs[n] = new_cost
partents[n] = node
processed.append(node)
node = fine_lowest_cost_node(costs)
print costs
Ｋ鄰近算法
#-*-coding:utf-8-*-
import heapq
from math import sqrt
day = [1,2,3,4,5]
holiday = [0,1]
activity = [0,1]
history_data = {'a':[5,1,0,300],'b':[3,1,1,225],'c':[1,1,0,75],
'd':[4,0,1,200],'e':[4,0,0,150],'f':[2,0,0,50]}
today = [4,1,0,0]
disposed = {}
for letter,data in history_data.items():
r = 0
for i in range(len(data)-1):
r +=pow(data[i]-today[i],2)
print letter+" : "+ str(r)
disposed[letter]=r
result = 0
h= heapq.nsmallest(4,zip(disposed.values(),disposed))
for i in h:
for a in history_data[i[-1]][-1:]:
print a
result += a
print result/4.0
二叉查詢樹
class Node():
def __init__(self,key=-1):
self.key = key
self.rnode = None
self.lnode = None
def insert(root,key):
if root==None:
root=Node(key)
else:
if key <root.key:
root.lnode = insert(root.lnode,key)
elif key >root.key:
root.rnode = insert(root.rnode,key)
return root
def query(root,key):
if root == None:
print 'no'
return -1
elif root.key == key:
print 'yes'
return 1
else:
if key <root.key:
return query(root.lnode,key)
elif key >root.key:
return query(root.rnode,key)
def show(root):
if root==None:
return
print root.key
show(root.lnode)
show(root.rnode)
root = Node(3)
insert(root,1)
insert(root,4)
insert(root,2)
query(root,1)
show(root)
