排序之直接插入排序

前言

本篇博客是在伍迷兄的博客基础上进行的，其博客地址点击就可以进去，里面好博客很多，我的排序算法都来自于此；一些数据结构方面的概念我就不多阐述了，伍迷兄的博客中都有详细讲解，而我写这些博客只是记录自己学习过程，加入了一些自己的理解，同时也希望给别人提供帮助。

前提故事

　　相信大家都玩过扑克，特别是斗地主；从你摸完第一张牌开始，之后的每摸的一张牌都需要与手中已有的牌进行比较，来确定这张牌放的位置，不管你们是否有这个习惯，我是有这个习惯的，就是从左到右，牌是从小到大的；这个摸牌的过程其实就是直接插入排序的一个过程；这时候有人就说了：我摸牌都不看牌的，等摸完了，再去整理牌，其实你这是找抽的节奏呀，别人都叫地主了，你还在整理牌！你说你是不是找抽。

　　开个玩笑，闲话不多扯，进入下面的正题。

基本思想

　　直接插入排序就是将一个记录插入到已经排好序的有序表中，从而得到一个新的有序表；最初的状态则是将整个序列看成是由第1个元素组成的有序序列 加 第2个元素至第n个元素的无序序列，这个两个序列组成的，如下图：

重点

　　将第2个无序列表中的元素逐个插入到第1个有序序列中，最终使得整个序列有序，如下图：

代码实现

　　代码实现语言采用java，没学过java的也没关系，只要有编程语言基础，就不影响阅读

/**
     * 直接插入排序
     * @param arr 目标数组
     */
    public static void strainghtInsertSort(int[] arr){
        int len = arr.length;
        // 将元素arr[i]插入到有序列表中arr[0...j]
        for(int i=1; i<len; i++){                            // 将arr[i]插入到有序列表
            for(int j=i-1; j>=0&&arr[j]>arr[j+1]; j--){        // arr[0...j]是有序列表
                swap(arr,j,j+1);
            }
        }
    }
    
    /**
     * 元素交换
     * @param arr
     * @param pos
     * @param offset
     */
    public static void swap(int[] arr,int pos,int offset){
        int temp = arr[pos];
        arr[pos] = arr[offset];
        arr[offset] = temp;
    }

执行过程模拟

可能基本思想大家懂了，但是不一定能把代码写出来，现在我把代码已经给出来了，可能又不一定能理解代码为什么这么写，那么我们就来模拟一些计算机执行上面程序的过程，这个过程之后大家就理解了。

　　1）程序从strainghtInsertSort方法（函数）开始执行，i=1，那么j=0，j满足条件j>=0&&arr[j]>arr[j+1]，那么交换arr[j]和arr[j+1]，此时，状态如下：

　　　　此时j--后，j=-1，不满足条件j>=0&&arr[j]>arr[j+1]，跳出内层循环

　　2）那么接着执行外层循环，i++后，i=2，那么j=i-1，则j=1，不满足条件j>=0&&arr[j]>arr[j+1]，跳出内层循环，此时状态如下：

　　3）与上一步一样，i=3时，则j=2，不满足条件j>=0&&arr[j]>arr[j+1]，跳出内层循环，此时状态如下：

　　4）重点看这一步，此时i=4,那么j=3，j>=0&&arr[j]>arr[j+1]条件满足，执行循环体，交换arr[3]和arr[4],得到如下状态：

　　　　乍一看，上面的有序序列变成无序了呀！博主，你这有问题呀！别急，毛都没长齐，就想要老婆，那怎么行了！接着往下走，此时执行j--，则j=2，j>=0&&arr[j]>arr[j+1]条件满足，执行循环体，交换arr[2]和arr[3],得到如下状态：

　　　　问题又来了，你这有序的序列不还是无序吗，还是有问题呀；骚年，别急，一口吃不成一个胖子，接着往下看，继续j--，j=1，j>=0&&arr[j]>arr[j+1]条件依然满足，交换arr[1]和arr[2],得到如下状态：

　　　　这次骚年学乖了，不说话了，那么我们接着往下看，依旧j--，j=0，j>=0&&arr[j]>arr[j+1]条件依然满足，交换arr[0]和arr[1],得到如下状态：

　　　　此时骚年惊讶了，哎呀，有序了！ 惊讶之后，别忘把程序跑完，j--，j=-1，j>=0&&arr[j]>arr[j+1]条件不满足，跳出内层循环

　　　　那么i=4时的最终状态如下：

　　同理，当i=5，6，7，8时，过程和上述一样，我这就不复述了，不过，心急的骚年还是要去把5，6，7，8执行完哦！

难以理解之处

基本思想其实好理解，可能内层循环的判断条件 j>=0&&arr[j]>arr[j+1]有点不太好理解，其实你根据上述的模拟过程应该能理解；

　　　此时骚年说话了，我理解呀，这有什么不能理解的，好吧，博主小瞧骚年了，博主刚接触这个算法的时候，j>=0&&arr[j]>arr[j+1]还真卡了我一会，模拟执行几次之后才理解；骚年果然比博主厉害呀！