算法导论1.2 插入排序

这个小结主要是用插入排序法，讲了一下什么是“循环不变式”，这个方法主要是用来证明你的算法是OK的，用python实现一下书里面的例子

arr = [5, 2, 4, 6, 1, 3]
for i in range(len(arr)):
    cursor = arr[i]
    pos = i
    while pos > 0 and arr[pos - 1] > cursor:
        arr[pos] = arr[pos -1]
        pos = pos - 1
    arr[pos] = cursor
    print(arr[:i+1])

输出如下，这个算法也好理解，想象一下斗地主时，刚开始摸牌，一张一张拿过来时在自己手里排序的情形，当拿到一张新的牌，和最边上的比一下，如果比这个小，再跟倒数第二个比，直到不比它小的时候插进去，这样手里的牌就一直是排好序的，等牌都发完，一眼就能看出是不是可以抢地主了

[5]
[2, 5]
[2, 4, 5]
[2, 4, 5, 6]
[1, 2, 4, 5, 6]
[1, 2, 3, 4, 5, 6]

循环不变式分三部分，初始化，保持，终止。看完书我觉得应该是这么理解，在第一次循环时只有一个5，排序OK，这说明初始化被证明成立；当开始循环时，每一次循环，就是咱们输出的这个子数组，都是排序OK的，那可以证明保持阶段成立；在排序完成后可见是OK的，这样就可以证明，终止成立。通过这三个阶段的证明，就可以断定，更多的数据放进来，仍然是排序OK的，那这个算法就没问题。当然，插入排序比较典型，特征很明显。