排序算法的学习之路——插入排序（概念篇）

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

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

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

这里面又涉及到了两个概念时间复杂度和空间复杂度在本篇不对这两个概念进行说明，我会在其他博文中来阐述一下我是如何理解这两个概念的。

由于篇幅问题本章不涉及到任何代码，仅仅分享一下自己对插入排序的理解。后续在其他的文章中为大家奉上本人写的每一种方法的实现代码。