迹忆客 专注技术分享

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

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

我们不妨将其转换成整队问题：开始会有两队，其中一队是按从低到高的顺序排列的，将其命名为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、表插入排序

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