MIT6.006是算法导论课，Lec03主要讲插入排序，归并排序，以及分析方法（递归树）等。
插入排序，可以分为线性插入排序、二分插入排序，区别在于当把数组中某元素插入到前面的有序列表中时，前者遍历，后者二分，后者更加稳定。
归并排序，是用分治思想处理，先分别排序，再合并。
递归树，我的理解是算法消耗时间T(n)用树状的结构，表示每次递归消耗的时间，这些时间累加就是T(n),而递归树的每一行和相邻行之间的关系也是比较容易观察的，这就容易写出时间复杂度的表达式了。另外有主定理可以使用。
参考了《算法导论》和网络上的资源，以下是我修改后的代码：
#coding:utf8
#插入排序 版本1（线性插入排序）
def insertion_sort1(a):
for j in range(1, len(a)):
key = a[j]
i = j - 1
while i>=0 and a[i]>key:
a[i+1] = a[i]
i = i-1
a[i+1] = key
if __name__ == '__main__':
array = [2,2, 4, 32, 64, 34, 78, 23, 2345, 12, 1, 3, 2]
insertion_sort1(array)
for a in array:
print a
# coding:utf8
# 插入排序 版本2（二分插入排序）
def binInsertSort(a): n = len(a) for j in range(1, n): key = a[j] i = j - 1 if key > a[i]: continue l, r = 0, i while l <= r: #print l, r mid = (l + r) / 2 if key < a[mid]: r = mid - 1 else: l = mid + 1 k = j while k > l: a[k] = a[k - 1] k = k - 1 a[l] = key if __name__ == '__main__': array = [2, 2, 4, 32, 64, 34, 78, 23, 2345, 12, 1, 3] insertsort(array) for a in array: print a
#coding:utf8
#归并排序
#MIT6.006 Lec03
def merge_sort(a, l, r):
'''归并排序主程序'''
if l < r:
m = (l + r) / 2
merge_sort(a, l, m)
merge_sort(a, m + 1, r)
merge(a, l, m, r)
def merge(a, l, m, r):
'''归并两个有序表'''
left = a[l:m+1]
right = a[m+1:r+1]
len1 = len(left)
len2 = len(right)
i, j, k = 0, 0, l
while i<len1 and j < len2:
if left[i] < right[j]:
a[k] = left[i]
i = i + 1
else:
a[k] = right[j]
j = j + 1
k += 1
while i<len1:
a[k] = left[i]
k += 1
i += 1
while j<len2:
a[k] = right[j]
k += 1
j += 1
if __name__ == '__main__':
array = [2, 2, 4, 32, 64, 34, 78, 23, 2345, 12, 1, 3, 2]
merge_sort(array, 0, len(array)-1)
for a in array:
print a
