迹忆博客
当前位置: 主页 > 学无止境 > 算法 > 文章

排序算法的学习之路——插入排序(概念篇)

发布时间: 2015-12-23 作者: 迹忆 浏览次数:

何谓‘插入排序’? 其概念如是说:每次将一个待排序的记录,按其关键字大小插入到前面已经排序好的序列中,直到全部记录插入完成为止。

概念的东西总是有些抽象,也可称其为基本思想。上述插入排序的概念同样也可说是插入排序的基本思想。抽象的东西理解起来总是有些困难,因此这里需要的是将抽象的概念具体化。

我们不妨将其转换成整队问题:开始会有两队,其中一队是按从低到高的顺序排列的,将其命名为A队。另一队是无序的,将其命名为B队。如下图:

现在把B队的第一个人(不妨称其为jack)放到A队中,并且保持A队依然是有序的,为了保持A队依然有序就需要在A队中找一个适当的位置给jack,这个位置前面的人要比jack矮,后面的人要比jack高。现在就可以让jack站到这个位置上面,此时A中依然有序。

然后再把B队的第二个人(称其为tom)放到A队,方式和jack相同,要保证A队依然有序。

依次类推直到B队的人全部站到A队当中。到此为止,两队合成了一队,而且这一队是有序的。

看到这对插入排序应该有一个比较清晰的认识了。但是这里还存在着一个疑问,排序问题是对一个队列进行排序,何来的两队呢。我们不妨再来转换一下,起初的时候A、B两队站在同一列,并且A队整体在B队前面,并且A队是一个人。对于一个人的队列肯定是有序的。


然后再向代码方面靠近一下,不妨将A、B两队映射成数组。有这样一个数组

其中 3 就表示 刚开始的A队 ,5、2…. 表示刚开始的B队。而5 就是 Jack, 2 就是Tom。

我当时学习插入排序的时候就是按照这个思路来理解的。到这里我对插入排序的思想基本上已经完全掌握了。

思想的东西转换成代码,不同的方式也会产生不同的‘派系’。好比《春秋经》读起来总是有些难懂,这时就有人出来为春秋作传,不同的人作出来的传也是不同的,有《左传》,有《公羊传》,有《谷梁传》 。 虽然有所不同,但是整体都是传承的《春秋》的思想 。

现在回到我们的插入排序上来,既然思想的东西都已经明了了,无非就是实现方式的差别。关键的地方还是在于A队,当在A队为B队的人查找适当位置的时候,查找的方式有很多种。
    1、每次开始从头遍历查找位置 称其为 直接插入排序
    2、用二分法查找位置 称其为 二分插入排序/折半插入排序

以上两种方式 都是在一个队列中查找和移动元素,主要时间花费在查找和移动两个方面。
还有第三种方式就是借助额外的队列,来做一个映射,这样可以省去了移动所花费的时间。
就是用空间换时间的做法,这种方式被称为:
    3、表插入排序

这里面又涉及到了两个概念 时间复杂度 和 空间复杂度 在本篇不对这两个概念进行说明,我会在其他博文中来阐述一下我是如何理解这两个概念的。
由于篇幅问题本章不涉及到任何代码,仅仅分享一下自己对插入排序的理解。后续在其他的文章中为大家奉上本人写的每一种方法的实现代码。

赞助
迹忆博客

上一篇:没有了

下一篇:排序算法的学习之路——直接插入排序

除非注明转载,本站文章均为原创,欢迎转载,转载请以链接形式注明出处

本文地址: