美文网首页
算法导论1.2 插入排序

算法导论1.2 插入排序

作者: 笑靥千年 | 来源:发表于2020-05-15 10:45 被阅读0次

    这个小结主要是用插入排序法,讲了一下什么是“循环不变式”,这个方法主要是用来证明你的算法是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的,那这个算法就没问题。当然,插入排序比较典型,特征很明显。

    相关文章

      网友评论

          本文标题:算法导论1.2 插入排序

          本文链接:https://www.haomeiwen.com/subject/venqohtx.html