超详解内部排序算法之（三）简单插入排序

简单插入排序

简单插入排序的基本介绍

简单插入排序，是对于将要排序的元素以插入的方式寻找该元素的适当位置，以达到排序的目的。

简单插入排序的思想

插入排序的基本思想是：把N个待排序的元素看做一个有序表和一个无序表，开始时有序表中只包含一个元素（即第一个元素），无序表中包含有N-1个元素，排序过程中每次从无序表中去除第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它 插入到有序表中的适当位置，是指成为新的有序表。
大家对于表述的思想有点抽象不好理解，我们通过图示来让大家跟直观的感受一下插入排序的处理逻辑，更好的理解这个处理思想

简单插入排序的思路图解

同样的，我们通过对于数组[12,4,9,112,-6,5]进行演示对应的插入排序的详解

插入处理过程

我们先将第一个元素即下标为零的【12】看做是一个有序列表，把剩余部分看做是另一个无序列表，依次从无序列表中从左到右选择对应的数据与有序列表从右到左比较（因为左边的有序列表是有序的，当遇到第一位某一个位置的值小于无序数据中拿出来进行操作的数的时候，就将对应的操作元素插入在这个某一位置的之后，左边的数组还是有序的，最终结束之后左边数组就形成了一个有序的序列），我们通过下述的详解插入排序处理过程可以更好的理解。
代码实现

public static void insertSort(int[] array){

        for (int i = 1; i < array.length; i++) {
            int value=array[i];//待操作的数字
            int insertIndex = i-1;//比较前一个位置insertIndex

            while(insertIndex>=0 && value<array[insertIndex]){//防止数组越界，最多也是到数组的第一个元素，即索引为零的下标
                //我们已经保存在待操作的数字，将对应的操作数字与最终交换插入问题的值变一致
                //
                array[insertIndex+1] = array[insertIndex];
                insertIndex--; 
            }
            //然后将insertIndex位置的值替换为操作数
            array[insertIndex+1]=value;
            //System.out.println("第"+(i+1)+"步操作的结果为："+ Arrays.toString(array));
        }
    }

---

插入过程详解

图标说明
橙色向下箭头表示操作的元素
绿色向上箭头表示参与比较的元素
左边五边形数据表示该数据什么时候插入

代码实现详解过程

老规矩，我们按照推导过程一步一步进行，先发现规律，在进行一步到位的处理

		
        //第一步，我们先看第一次的排序
        //[ 12	4	9	112	-6	5]
        //
        //[ 4    12	9	112	-6	5]
        //value=4
        //valueIndex=1

        int value=array[1];//待操作的数字
        int insertIndex = 1-1;//比较前一个位置insertIndex

        while(insertIndex>=0 && value<array[insertIndex]){//防止数组越界，最多也是到数组的第一个元素，即索引为零的下标
            //我们已经保存在待操作的数字，将对应的操作数字与最终交换插入问题的值变一致
            //
            array[insertIndex+1] = array[insertIndex];
            insertIndex--;
            //我们得到的应该是这样的一个数组[ 12   12	9	112	-6	5]
        }
        //然后将insertIndex位置的值替换为操作数
        array[insertIndex+1]=value;
        System.out.println("第一步操作的结果为："+ Arrays.toString(array));

        //第二次操作
        //这次我们操作第三个元素，也就是索引index=2的元素
         // value =array[2] 9
         // 拿9 和前一个元素即12作比较
         //
         //
        value=array[2];//待操作的数字
        insertIndex = 2-1;//比较前一个位置insertIndex

        while(insertIndex>=0 && value<array[insertIndex]){
            //我们已经保存在待操作的数字，将对应的操作数字与最终交换插入问题的值变一致
            array[insertIndex+1] = array[insertIndex];
            insertIndex--;
            //我们得到的应该是这样的一个数组[ 4   12	12	112	-6	5]
        }
        //然后将insertIndex位置的值替换为操作数
        array[insertIndex+1]=value;
        System.out.println("第二步操作的结果为："+ Arrays.toString(array));

        value=array[3];//待操作的数字
        insertIndex = 3-1;//比较前一个位置insertIndex

        while(insertIndex>=0 && value<array[insertIndex]){
            //我们已经保存在待操作的数字，将对应的操作数字与最终交换插入问题的值变一致
            //
            array[insertIndex+1] = array[insertIndex];
            insertIndex--;
            //我们得到的应该是这样的一个数组[ 4   9	12	112	-6	5]
        }
        //然后将insertIndex位置的值替换为操作数
        array[insertIndex+1]=value;
        System.out.println("第三步操作的结果为："+ Arrays.toString(array));

        value=array[4];//待操作的数字
        insertIndex = 4-1;//比较前一个位置insertIndex

        while(insertIndex>=0 && value<array[insertIndex]){//防止数组越界，最多也是到数组的第一个元素，即索引为零的下标
            //我们已经保存在待操作的数字，将对应的操作数字与最终交换插入问题的值变一致
            //
            array[insertIndex+1] = array[insertIndex];
            insertIndex--;
            
        }
        //我们得到的应该是这样的一个数组[ 4   4   9	12	112	5]
        //然后将insertIndex位置的值替换为操作数
        array[insertIndex+1]=value;
        System.out.println("第四步操作的结果为："+ Arrays.toString(array));

		 value=array[5];//待操作的数字
        insertIndex = 5-1;//比较前一个位置insertIndex

        while(insertIndex>=0 && value<array[insertIndex]){//防止数组越界，最多也是到数组的第一个元素，即索引为零的下标
            //我们已经保存在待操作的数字，将对应的操作数字与最终交换插入问题的值变一致
            //
            array[insertIndex+1] = array[insertIndex];
            insertIndex--;
            
        }
        //我们得到的应该是这样的一个数组[ -6   4   9    9	 12	112]
        //然后将insertIndex位置的值替换为操作数
        array[insertIndex+1]=value;
        System.out.println("第五步操作的结果为："+ Arrays.toString(array));
        //结果：[ -6   4   5    9	 12	112]

		

归纳规律

for (int i = 1; i < array.length; i++) {//我们从下标为1的开始比较，因为我们默认第一个为有序的数组
            int value=array[i];//待操作的数字
            int insertIndex = i-1;//比较前一个位置insertIndex

            while(insertIndex>=0 && value<array[insertIndex]){//防止数组越界，最多也是到数组的第一个元素，即索引为零的下标
                //我们已经保存在待操作的数字，将对应的操作数字与最终交换插入问题的值变一致
                //
                array[insertIndex+1] = array[insertIndex];
                insertIndex--;
               
            }
            //然后将insertIndex位置的值替换为操作数
            array[insertIndex+1]=value;
            //System.out.println("第"+(i+1)+"步操作的结果为："+ Arrays.toString(array));
        }

结果验证

我们在自己的机器上实验一下是否结果如我们分析一样。

和我们的分析结果一样，代码OK。

我们接下来看看插入排序的效率，我们依旧选择80000个数据进行测试一把

public static void main(String[] args) {
        int[] array = new int[80000];
        for (int i = 0; i < array.length; i++) {
            array[i]=(int)(Math.random()*800000);
        }
        System.out.println("插入排序！！");

        Date dateStart = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        System.out.println("Front of Execute:"+simpleDateFormat.format(dateStart));

        insertSort(array);
        Date dateEnd = new Date();
        System.out.println("Front of Execute:"+simpleDateFormat.format(dateEnd));
    }

执行结果显示

相较于选择排序的处理，插入排序的处理更快一点，效率更高一点。

插入排序到此OK，小伙伴可以在自己的机器上边实现一把，加深对应的影响，实现不是最重要的，理解其内在的思想和排序的逻辑才是我们care 的事情。fighting。