总结算法图解知识点

二分查找

• Ｏ(log2*n)
• 有序的元素列表

import math
#导入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])

广度优先查找

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)