搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库
Lambda在线 > 达内直播课 > 算法图解-简单插入排序算法

算法图解-简单插入排序算法

达内直播课 2018-11-10
举报

曾几何时一位帅气大爷(John E. Hopcroft)说出了一句话:”程序设计=数据结构+算法“,因而获得计算机最高奖项-图灵奖。

大爷的简介是酱紫的,请各位收好下巴。

算法图解-简单插入排序算法


 12

       霍普克洛夫特

  • 美国康奈尔大学智能机器人实验室主任

  • 计算机科学系工程与应用数学的IBM教授

  • 世界计算机科学最高奖图灵奖获得者

  • 美国国家科学院和工程院院士

  • 现任香港中文大学(深圳)霍普克罗夫特高等信息科学研究院院长。


所以小编觉得你大爷终归是你大爷。

算法图解-简单插入排序算法

今天小编就要带大家走入算法的世界,十种常见排序算法可以分为两大类:

非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序。

线性时间非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此称为线性时间非比较类排序。 

时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。

空间复杂度:是指算法在计算机内执行时所需存储空间的度量,它也是数据规模n的函数。 

看完这个解释是不是很懵逼,不要急,容小编喝口水给大家用人类语言讲解

算法图解-简单插入排序算法

其实很好理解,时间复杂度就是排好顺序需要花费的时间,排序时间越久代表此排序算法效率越低。而空间复杂度呢就是排序所消耗的内存,消耗内存越多,算法效率也越低。

算法图解-简单插入排序算法

简单入排序简介

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

算法描述

一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

  1. 从第一个元素开始,该元素可以认为已经被排序;

  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;

  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;

  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;

  5. 将新元素插入到该位置后;

  6. 重复步骤2~5。


视频演示

代码演示


算法分析

插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

最后小编为大家奉上一张图片以示鼓励,如果各位小主对非线性时间理解不是很到位,大家去看看《降临》这部电影,相信小主们会有新的认识。


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《算法图解-简单插入排序算法》的版权归原作者「达内直播课」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

举报