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] = keyif __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] = keyif __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 Lec03def 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