倚楼听风雨
淡看江湖路

浅析数据结构排序篇之插入排序 Insertion Sort

数据机构笔记之路很遥远,但是老四没有忘记,依然按照自己的节奏更新着自己关于技术的理解,尽可能的说的明白一些,希望对能看到的人有所帮助。本文要讲的是插入排序,相对来说是比较基础的排序算法。

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序的数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用 in-place 排序,因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

原地算法(摘自维基百科)

原地算法(in-place algorithm)基本上不需要额外辅助的数据结构,然而,允许少量额外的辅助变量来转换数据的算法。当算法运行时,输入的数据通常会被要输出的部分覆盖掉。不是原地算法有时候称为非原地(not-in-place)或不得其所(out-of-place)。

一个算法有时候会错误地被称为原地算法,只因为它用它的输出数据会覆盖掉它的输入数据。事实上这条件既不充分(在快速排序案例中所展示的)也非必要;输出数据的空间可能是固定的,或如果以输出为流数据而言,也甚至是可能无法被数清楚的。另一方面来看,有时候要决定一个算法是不是原地,而数它的输出空间可能是比较可行的,像是底下的第一个的reverse示例;如此使得它更难去严格地定义原地算法。在理论上的应用像是log-space reduction,更是典型的总是忽略输出的空间(在这些状况,更重要的是输出为仅能写入)。

老样子,还是将算法动画图解的动态展示一下,看起来更直观一些。

浅析数据结构排序篇之插入排序 Insertion Sort的图片-高老四博客

如果觉得 gif 加载太快可以下载下来使用播放器暂停查看

Java 代码模拟插入排序基本实现

综上,插入排序属于基本的排序算法,是我们必须要掌握的排序算法。在排序的分类中,我们都知道插入排序、交换排序、选择排序和归并排序都归属于内排序,插入排序的时间复杂度:O(n²),不是很优秀,但是就像和冒泡一样,十分基础,务必重视。

更博不易,如果觉得文章对你有帮助并且有能力的老铁烦请捐赠盒烟钱,点我去赞助。或者扫描文章下面的微信/支付宝二维码打赏任意金额(点击「给你买杜蕾斯」),也可扫描小站放的支付宝领红包二维码,线下支付享受优惠的同时老四也可以获得对应赏金,老四这里抱拳谢谢诸位了。捐赠时请备注姓名或者昵称,因为您的署名会出现在赞赏列表页面,您的捐赠钱财也会被用于小站的服务器运维上面,再次抱拳感谢。

赞(4) 给你买杜蕾斯
本站原创文章受自媒体平台原创保护,未经允许不得转载高老四博客 » 浅析数据结构排序篇之插入排序 Insertion Sort
分享到: 更多 (0)
4万+首WAV无损音乐仅需 28 元 赠送24bit合集、DSD音乐、歌手合集、欧美影视原声及本站发布过的音乐

开始你的表演 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下老四,鼓励我更好的创作

支付宝扫一扫打赏

微信扫一扫打赏