最近在上MIT的6.006算法课，重新温习了下排序算法，发现很多知识点以前并没有吃透，也没有记下来，所以这次还是写在这里了。知之为知之，不知为不知嘛。

Insertion sort

核心

取出元素比较并插入到之前已经排好序的数组中。

例子

1. [3 5 2 1] # 取第二位5，比较第一3
2. [3 5 2 1] # 5 比 3 大， 略过
3. [3 5 2 1] # 取第三位2， 和第二位比较，2 比 5 小，2向前
4. [3 2 5 1] # 继续比较2 和 3， 2 比 3小，2向前
5. [2 3 5 1] # 1就重复上述步骤

代码

def insert_sort(a):
for i in xrange(1, len(a)):
v = a.pop(i)
p = bisect.bisect(a[:i], v)
a.insert(p, v)
return a

Merge sort

核心

合并已经排好序的两个数组，哪个符合条件就添加到结果里。

合并时，对两个数组头元素作出对比，又称"两指合并"

例子

1. [3 5] [2 1] # 拆成两个数组，并给他们排序
2. [3 5] [1 2]
3. R:[1] Stack:[3 5] [2] #两个数组里1 最小，添加到结果里
4. R:[1 2] Stack:[3 5] # 继续比较2 和 3， 2 比 3小，2添加到结果里
5. ＃就重复上述步骤

代码

def merge_sort(a):
la = len(a)
if la == 1:
return a
elif la == 2 and a[0] > a[1]:
a[0], a[1] = a[1], a[0]
return a
else:
left, right = merge_sort(a[:la/2]), merge_sort(a[la/2:])
result = []
while left and right:
if left[0] < right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
if left:
result += left
if right:
result += right
return result

Quick sort

个人最喜欢的一个算法，简单，快速！但是对栈的调用较多～

核心

和MergeSort 很像，也是合并已经排好序的两个数组，但是是哪个符合条件就放入递归的qsort里。

可以说两个是一前一后。

代码

def qsort(a):
la = len(a)
if la <= 1:
return a
elif la == 2 and a[0] > a[1]:
a[0], a[1] = a[1], a[0]
return a
else:
lt, gt = [], []
for x in a[1:]:
if x > a[0]:
gt.append(x)
else:
lt.append(x)
return qsort(lt) + [a[0]] + qsort(gt)

Heap sort

核心

借助Heap（堆）的特性：最大／小的元素会在数组的头部，进行排序。

知识点

heap是一种由数组构成的特殊二叉树结构，具体在下面的思维导图里。

代码

def heap_sort(a):
la = len(a)
def heapify(start, end):
father = start
while True:
child = father * 2 + 1
if child > end:
break
if child + 1 <= end and a[child] < a[child+1]:
child += 1
if a[father] < a[child]:
# swap
a[father], a[child] = a[child], a[father]
father = child
else:
break
# la/2 -> 0
for i in xrange((la-2)//2, -1, -1):
heapify(i, la-1)
# la -> 0
for end in range(la-1, 0, -1):
a[0], a[end] = a[end], a[0]
heapify(0, end-1)
return a

随机输入比较图

#数据结构与算法