美文网首页
算法导论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 插入排序

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

  • lecture 1

    算法导论Lesson1 课程简介: 内容主要包括: 算法的含义、意义的简要介绍; 算法的分析; 插入排序、合并排序...

  • 2018-08-08 算法导论(2.1 插入排序)

    算法导论学习101 首先,对于插入排序算法的大致描述为下输入为: < a1, a2, a3, ... , an >...

  • 第1天-插入排序

    算法说明 插入排序是算法导论一书中第一个算法,在书中举了一个非常恰当的扑克牌例子来说明插入排序的算法原理:Inpu...

  • 算法导论-插入排序

    1.伪代码 算法流程图示 2.Python代码 result: 循环不变性: 初始化: 循环的第一次迭代之前,他为...

  • 插入排序【算法导论】

    注:学习算法导论,按照标准伪代码理解翻译为java实现,如有兴趣理解整个过程的细节,建议阅读《算法导论》第二章:2...

  • 讨厌算法的程序员 1 - 插入排序

    讨厌算法的程序员系列入口 什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般...

  • 数据结构与算法(七),排序

    这节总结一下常见的排序算法。 目录: 1、插入排序 1.1、直接插入排序 1.2、二分插入排序 2、选择排序 3、...

  • 排序算法入门之「插入排序」

    插入排序 借用《算法导论》里的例子,就是我们打牌的时候,每新拿一张牌都会把它按顺序插入,这,其实就是插入排序。 齐...

  • 算法导论-算法基础-插入排序

    插入排序 输入:n个数的一个序列 。输出:输入序列的一个排列 ,满足a1'≤a2'≤…≤an'。 j表示正准备插入...

网友评论

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

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