基础算法概念：

时间复杂度

时间复杂度是从其增速的角度度量的，

时间复杂度一般用大O法表示。

递归

递归指的是调用自己的函数。

如果使用循环，程序性能可能更高；

如果使用递归，程序可能更容易理解。

基线条件：函数不再调用自己的条件，

递归条件：函数调用自己的条件。

二分法查找（递归）（时间复杂度O(logn)）：

def binary_search(arr, key):
left = 0
right = len(arr) - 1
while right >= left:
mid = (left + right)/2
if key > arr[mid]:
left = mid + 1
elif key < arr[mid]:
right = mid - 1
else:
return mid
return -1

a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print binary_search(a, 11)

选择排序（时间复杂度O(n2)）：

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

print selectionSort([5, 3, 6, 2, 10])

快速排序（递归）（时间复杂度O(nlogn)）：

def quicksort(array):
if len(array) < 2: return array # 基线条件：为空或只包含一个元素的数组有序 else: pivot = array[0] # 递归条件 lesser = [i for i in array[1:] if i <= pivot] # 所有小于等于基准值的元素组成数组 greater = [i for i in array[1:] if i > pivot] # 所有大于基准值的元素组成数组
return quicksort(lesser) + [pivot] + quicksort(greater)

print(quicksort([10, 5, 2, 3]))

快速排序（非递归）：

# -*- coding:utf-8 -*-
from collections import deque

def quick_sort(arr):
deq = deque([0, len(arr) - 1])
while deq:
low = deq.popleft()
l = low
high = deq.popleft()
h = high
pivot = arr[low]
while high > low:
while high > low and arr[high] > pivot:
high = high - 1
arr[high], arr[low] = arr[low], arr[high]
while high > low and arr[low] < pivot:
low = low + 1
arr[high], arr[low] = arr[low], arr[high]
arr[high] = pivot
m = high
if m != l:
deq.append(l)
deq.append(m - 1)
if m != h:
deq.append(m + 1)
deq.append(h)
return arr

print quick_sort([24, 2, 3, 23, 4, 7, 5])

冒泡排序：

def bubblesort(array):
for i in range(len(array)):
for j in range(len(array)-1-i):
if array[j] < array[j+1]:
array[j], array[j+1] = array[j+1], array[j]

p = [1, 7, 9, 2, 3, 4, 5, 5]
bubblesort(p)
print p

归并排序：

def merge(arr1, arr2):
arr = []
while len(arr1) != 0 and len(arr2) != 0:
if arr1[0] > arr2[0]:
arr.append(arr1.pop(0))
else:
arr.append(arr2.pop(0))
return arr + arr1 + arr2

def mergeSort(array):
if len(array) < 2:
return array
mid = len(array) / 2
left = mergeSort(array[:mid])
right = mergeSort(array[mid:])
return merge(left, right)

c = [2, 6, 4, 0, 8, 5, 3]
print mergeSort(c)