继续接着上一次https://www.cnblogs.com/webor2006/p/14014542.html的排序算法夯实基础，上次是选择排序，这次则是插入排序了，其学习路线基本跟上一次雷同~~

生活场景：

先来对插入排序的思想进行一个了解，了解的场景从我们打扑克开始：

当我们手中抓到图中所示的几张牌时，你是怎么样将它从小到大的顺序进行排列的呢？其实插入排序直观的感觉就是如你针对此场景的一个排序，这里以具体下面的这一手排进行排序为例进一步感受下它的思想：

好，下面来对它进行从小到大的顺序进行排序：

1、从左边拿出一张牌8，很显然它木有可比较的，放在原地不动。

2、再拿出牌6，用它跟它前面的牌8进行比较，发现比8要小，则需要将此牌放到8的前面，如下：

3、再拿出牌7，跟它前面的牌进行比较，发现它比6要大，比8要小，所以此时则将它放到6和8的中间，如下：

4、再拿出牌10，发现它前面的都比这张要小，则原地不动。

5、最后拿出9，跟之前的对比，插在8与10之间比较合适，如下：

至此，整个牌就已经从小到大进行排序了，其规律总结就是：“每次处理一张牌，把这张牌插入到前面已经排好序的牌中。”，其中插入标红了，也就是插入排序得名的原因之所在。

计算机场景：

接下来转换一下场景，由生活场景转换到咱们的计算机场景，再来看一下整个的排序过程，思想是雷同的，比如要排序的数据如下：

根据上一次的选择排序的分析思路，也是需要借助下标的，所以排序过程开始。

1、首先处理第0个元素：

而它的循环不变量其实跟快速排序的是一样的：“arr[0, i)已排好序；arr[i...n)未排序”，而思想就是把arr[i]放到一个合适的位置，对于第一个元素由于木有可比项，所以直接处理结果就是原地不动，很愉快的就处理了：

2、i++，接下来处理第二个元素：

接下来则就确定当前元素4应该插入到前面合适的位置了，那为了确定它所在的合适的位置，则还需要借助于一个下标：

其思路跟之前学习选择排序类似，发现它前面的j-1的元素6比j指向的4要大，那则交换一下位置，所以此时的形态为：

注意：此时j会跟着一起交换， 那j指向的这个4是否就是合适的位置了呢？此时还不知道，还得往它前面进行追溯，发现它前面已经木有元素了，那此时4就已经找到合适的位置啦：

找到之后，此时j就没有了，其实也就是内部循环就退出了，这块待撸码时再来体会。

3、i++，接下来处理第三个元素：

要想确定2在它之前合适的位置，依然又得借助于一个下标了：

然后对比j-1的元素6，发现比它小，此时2的合适位置应该是在6的位置，所以此时需要进行交换，交换后就变成：

注意：此时的j会跟着一起交换，然后又继续对比j-1的元素的大小，发现比4要小，则又要进行一次交换：

此时j=0，前面已经没有元素可以比较了，所以此时2这个元素就已经确定好了最合适的位置了：

4、i++，接下来处理第四个元素：

同样的套路，为了将3放到一个合适的位置，此时还得借助于j下标了：

然后拿j-1跟当前的元素进行大小比较，很明显此时j和j-1需要进行一下交换，变化：

继续对比j-1，发现j比j-1还要少，那此时j的位置很明显是不合适的，交换让其变得合适：

那此时3的位置已经是最合适的么？还不知道，还得看j-1是否大于它，发现j-1是2很明显小于j，所以此时3就是一个非常合适的位置啦，所以3也处理好了：

接着继续i++，以此类推。。。这里再来回忆一下它的循环不变量是不是就是“arr[0, i)已排好序；arr[i...n)未排序”，然后维持这个循环不变量是通过“把arr[i]放到一个合适的位置”【关于这个循环不变量在未来的学习会不断强调，再强调下它很重要！！！！】，直接i走到n的位置，arr[0,n)都已经排好序了整个排序算法就已经结束了。

阐述选择排序和插入排序的区别：【重要】

对于上面分析的过程只分析到了四个元素，还剩下2个木有分析，其实是有目的的，因为要阐述一下关于选择排序和插入排序之间的区别呀，认识这种区别对于你排序算法的选型是很有帮助的，先回忆一下对于上次学习的选择排序的循环不变量中啥？

发现新大陆木有？很明显它们俩的循环不变量是一模一样的呀，好，下面看一张图，都是处理到了第四个元素，那处理完之后的结构对比一下，就能发现区别了：

可以看出选择排序对于已排序的元素一定【注意它，重点加粗】是整个数组中最小的那几个元素，回到图中对于1、2、3、4是已经排序好的，它们四个元素就是整个数组中最小的，这块其实是跟选择排序特性有关，因为对于每一次处理完一个位置之后就是当整个数据排序完毕之后这个位置应该存放的元素是谁？啥意思？比如说处理i=0位置存放的1就是数据排序完毕应该存放的位置：

同样的对于其它已排序的2，3，4也是一样的。

但是！！！！对于插入排序则不一样了，对于i之后的元素因为还没处理，所以完全是不会动它们的，因此回到图来看当用插入排序处理完四个元素之后，只是保证处理元素的位置是正确的，但是并不是最终排序完应该存放的位置了：

关于它们两者的不同的理解，其实比单纯学习两种排序算法的意义还要大，因为只有你清楚了各个算法的差异你才能在实际算法的决策上不会盲目挑选，而正是由于这样的不同，在后续就能看到插入排序有它非常独特的性质，至于这个性质是啥，到时分析时再说。

实现插入排序法：

接下来则来实现一下该算法，在上面已经对于算法的思路进行了一个清晰的梳理之后，其实实现起来也比较简单，本身就不是一个复杂的算法，下面开始，这里还是在上一次的工程中进行撸码，先新建一个类：

public class InsertionSort {
    private InsertionSort() {
    }

    public static <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            //TODO:将arr[i]插入到合适的位置
        }
    }
}

接下来就是如何将arr[i]插入到合适的位置了，如思想所述，需要借助另一个下标j从当前i的位置往前进行遍历，然后每次都合j-1的元素进行对比，如果比j-1小则交换，否则停止交换，也比较简单：

比较好理解，就不过多的解释了，接下来则实现数组元素的交换了，这个可以复用咱们上次选择排序的交换方法：

将其拷过来：

但是！！！此时对于内层的遍历还差一个退出的条件，其实就是发现j的元素不比j-1的小就可以退出了：

接下来测试一下，其测试方法跟上一次一样：

上面都是之前封装的代码就不做过多的解释了，只是这里需要再修改一下以便能调用到咱们的这个方法：

运行：

可以发现随着n扩大了10倍，时间耗时扩大了将近100倍，说明对于插入排序来说它的时间复杂度也是O(n^2)级别的，这里先有个初步印象，关于时间复杂度之后再分析，对于上面这个结果还记得是怎么来保证咱们的排序是正确的么？回忆一下上节的封装：

而由于咱们运行结果都正常打印了所以可以论证咱们的排序是正常的，关于这些回忆以后就不过多强调了。

算法初步优化：

接下来对咱们实现的算法进行一个小优化，其实算是一个小的代码调整吧，先来看一下咱们目前实现的：

对于这样的代码其实可以更加的简练，改成这样：

但是！！！对于上面两种写法其实都差不多，可能写法二的性能稍稍好那么一丢丢，可是对于一个算法而言像这种逻辑上的小优化其实可以忽略不计，所以在之后的算法学习中对于像这种优化就不再去讲究了，有时可能觉得写法二的逻辑会更加清晰呢~~

算法进一步代化：

思路：

在上面已经对于咱们实现的算法进行了一个小小的优化，接下来则有一个非常重要的优化点了，这个优化确确实实是能够带来性能上的提升的，优化点在哪呢？先来回忆一下对于咱们实现的插入排序的思想：

为了将3放到前面合适的位置，这里会借助j来跟前面的j-1的元素一一进行比较，于是乎此时会经过二次“交换”：

此时发现3已经是最合适的了，所以元素3就已经排好了：

其中的技法是用到了“交换”，我们知道两元素的交换是由三次操作完成的，如果说能优化这块的操作由三次变为一次，那是不是整体的排序性能定能大大增强？是的，这也是接下来要着手去解决的，其实对于上面的这种操作利用一次平移操作就可以达到目的了，这里仔细观察思考一下有木有这种可能？

呃，说得太抽象了。。没关系，下面图解一下这种新优化的思路，还是回到原始状态：

接着要找到3它的合适的位置，先将它暂存一下：

暂存的目的是为了当最后确定了合适的位置时直接平移过来，因为暂存了，所以此时这个位置那就可以随便被其它元素平移覆盖了：

不空出一个位置如何将元素进行平移呢是不是？好，而接下来就是如何确认元素3的一个合适位置了，方法跟之前的交换方式一样，无限跟j-1前一个元素进行比较，此时发现比6要小，所以直接将大的元素6往后平移一下：

此时咱们有元素3被平移的6覆盖了，木关系，因为待处理的3元素已经提前做备份啦，接下来继续来确认3的合适位置，此时j--

接下来继续判断j-1的元素跟3进行比较，发现4>3，此时又将4元素直接平移到j所在的位置，如下：

此时还得继续判断,j--：

同样拿j-1跟备份的3进行对比，发现2<3了，哦，此时j就是备份元素3应该存放的位置，此时直接进行一次赋值就可以确定最终3的位置啦：

此时循环就终止了：

但是！这块要预先知道一下，这种优化并不是“时间复杂度的优化”，啥意思？也就是既始我们这样优化了，其时间复杂度还是O(n^2)级别的，因为时间复杂度算的是一个最差的情况，可以这种实现方式是一个比较优的实现方式，这点需要明白。

具体实现：

基于上面的优化思想接下来落地到代码上来，为了之后跟目前已经实现的这种排序算法进行一个性能上的对比，这里再开一个方法进行实现：

先暂存一下arr[i]元素：

然后利用另一个下标j来确定arr[i]应该存放的合适位置的下标，所以可以先把框架写好：

而这个循环也比较简单，如下：

测试：

接下来咱们来测试一下，这里为了跟咱们之前实现的算法进行一个对比，测试用例这样改一下：

然后修改一下sortTest方法：

运行一下：

可以看到，当数据在100000级别时，sort2的这种性能比sort1要快了很多，因为减少了交换的执行指令嘛，但是！！！还是那句话，这个性能的提升并没有让这个算法的复杂度发生根本性的改变，所以也能看到虽说sort2在10万级别的数据排序时相比sort1是快了，可也得十几秒呀，在未来高级算法的学习中就会接触当真正算法的复杂度有了质的提升之后，对于10万，100万级别的数据都可以轻松在一秒以内甚至是零点几秒的时间内就完成这个排序过程，所以对于算法的优化主要是要针对“时间复杂度级别的优化”上，这也是我们学习算法的关键，而非要扣这种常数级别的优化。

另外由于这种sort2的实现方式是比较优的，所以以后对于插入排序算法的测试就用它了，而不用sort1，这点需要明确。

算法复杂度分析：

接下来咱们来分析一下咱们实现的算法的复杂度了，其实也不用分析了，从结果就可以看出来了是O(n^2)级别，不过这里再来稍加看一下既可：

所以这块复杂度就不过多的说明了。

分析插入排序法的特性【重要】：

阐述：

虽说这个算法的复杂度是O(n^2)级别，但是它有一个非常非常重要的特性需要阐述一下，因为这个特性在未来高级算法的学习中也会进行借鉴的，啥特性呢？下面来看一个极端的数据例子：

哦，本身该数据就已经是排好序的了，那咱们来看一下整个排序的过程是咋样的：

1、i=0：

很显然它不需要动，所以直接就确定了位置了：

2、i=1：

发现它前面的元素本身就小于2，那当前位置就是合适的位置了，直接确定了：

3、i=3：

发现它前面的元素已经小于3了，也是直接就确定了：

然后以此类推，发现如果待排序的数组已经是排了序的，其实对于内面的那个for循环其实每次只是判断了一下前面的值的大小就退出了，也就是说这种情况下这层循环变成了是常数级别的操作了，所以对于插入排序的一个非常重要的特性就出来了：“对于有序数组，插入排序的复杂度是O(n)的”，但是这个特性是上次学习的选择排序所不具备的哟，因为对于选择排序而言每次要想确定其最小值一定是要遍历所有的元素才能确定的，既使第一个元素已经是最小的，但是计算机是不知道的呀，所以还得遍历整个元素才能进行确定，所以要记住：“对于选择排序而言，它是稳定的O(n^2)级别的算法，不管数组是有序还是无序。”，但是！！！！还得记住一句话：“整体而言，对于排入排序的复杂度依然是O(n^2),因为算法复杂度看的是最差的情况，而非最好的情况”。

基于这样的特性，如果在实际中遇到近乎有序的数列要排序，要明白使用插入排序的性能是非常好的，在这时就不要选择选择排序了，最典型的就是银行的业务数据，基本上所有的业务数据都是按时间来处理的，只有少数的业务可能处理的时间较久会有乱序的情况，这样就是近乎有序的数据了。

实际验证：

接下来则用代码验证咱们上面所分析的特性，为了能更加清楚的认识到插入排序跟选择排序的区别，这里用两组测试数据，一组是随机乱序的数组，另一组是完全有序的数组，然后运行对比一下，一看结果就能深刻体会到两者的区别了，修改一下测试用例：

运行看一下：

从上面结构足以证明对于插入排序在一个近乎有序的数列中的时间复杂度会变为O(n)，性能非常得好。

换个角度实现插入排序法：

在最后为了进一步巩固对于插入排序算法的理解，打算从另一个角度来实现一下插入排序，其实在上一次的选择排序中也这么办过，也就是将循环不变量反过来实现，对于目前咱们的实现的循环不变量是：

arr[0,i)是已排好序的，而arr[i...n)是未排序的，那一个角度来实现那么就是将循环变量变为：arr[0,i)是未排好序的，而arr[i...n)是已排序的，其实现思路也比较简单，由之前的从左向右扫描改为从右向左，如下：

然后依然是暂存arr[i]，然后跟它之后的arr[i+1]进行大小比较，如果比arr[i+1]还要大，则说明暂存的位置还得靠后，当然还是借助于j这个新下标来找到合适的位置，具体内循环的条件就得改为：