排序算法（三）插入排序法

排序算法(三) 插入排序法

插入排序算法，冒泡排序算法，和选择排序算法三个合称三大基本排序算法，因为都是相对比较简单易懂的算法，相对来说算法的效率也是比较低的。但是这个插入排序算法比起冒泡选择来说难度还是高一点的，而且在学校中教授的也只有冒泡排序和选择排序，插入排序是没有教授的。

插入排序的基本介绍

插入排序算法是一种稳定的算法，和冒泡排序是一样的，相同的数据经过插入排序之后相对位置是不变的。

插入排序的基本思路

插入排序的思路是将待排序的数组分为两个数组，左面是有序的数组，右面是无序的数组，（一开始左边的第一个元素就自成一个有序数组，毕竟只有一个元素，怎么说都是有序的）然后将无序数组的第一个数据插入到有序的数组当中去。于是有序的数组越来越大，等到无序的数组中的所有的元素都插入到了有序的数组中的时候，排序就完成了。

对于无序的数据如何插入到有序的数组当中去有两个实现的办法。一个是交换法，另一个是移位法。上面的动图实现的就是交换法。让我们先从简单的交换法讲起。

插入排序——交换法的代码实现

感觉这个算法看一下上面的那个动图就能清楚的明白。就是如同冒泡排序法一样，如果要插入的数据被前面的数据小的话，两者交换数据，然后继续比较，直到插入的数据大于前面的那个数据(此时便插入到了合适的位置了)退出循环即可。

// 插入排序， 使用直接交换的方法，这样交换的次数就非常多了，效率就变低了
    public static void insertSort(int[] arr) {
        int temp;// temp用于下面的交换
        // 左面有一个数据是有序的，无序的数据是从第二个开始的，所以i的初始值为1
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {// 使用交换的方式来插入当前的数据
                if (arr[j] < arr[j-1]) {
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }else { // 如果上面的if不成立就说明这个数已经到达了指定的位置，因为左面的数组是有序的。
                    break;
                }
            }
        }
    }

代码说明：

1. i 为什么从一开始？

   ​ 因为插入的值是从无序开始的，而一开始arr[0]就是有序的，无序的从arr[1]开始，所以i是从1开始的。

2. j。。。好像没啥好说明的。这个代码还是非常容易理解的。还是叭说了QwQ

插入排序——移位法的实现

移位法不是交换数据来实现数据的插入，而是先把待插入的数据保存起来。然后依次与前面的有序的值进行比较。如果前面的值比待插入的值大的话，直接将前面的值赋给后面的值(就好像移动位置一样，前面的值将后面的值覆盖了)。然后继续比较。如果小于的话，直接将当前的位置赋予之前保存的那个待插入的值，然后退出本次循环。

// 采用的是移位法不是交换法，极大的提高了插入排序的效率
    public static void insertSortSgg(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];// 保存要插入的值
            int insertIndex = i; // 要插入的位置。。。
 
            // while循环找到了当前值应该插入的位置
            while (insertIndex > 0 && insertVal < arr[insertIndex-1]) {
                arr[insertIndex] = arr[insertIndex-1];// 将大的数据后移
                insertIndex--;
            }
            arr[insertIndex] = insertVal; // 插入数据
        }
    }

代码说明：

1. insertVal和insertIndex是干什么用的？

   • insertVal用于保存当前要插入的值，也就是后面的无序的数组的第一个元素。如果不保存的话，根据移位法，要插入的值将可能被前面的值覆盖，那还玩个蛇皮！
   • insertIndex是保存要插入的位置，初识值就是要插入的值的原本的位置（即没有发生移位）。

2. while循环写的是什么玩意，我为啥看不懂？？

   while循环里面的第一个条件是保存你不能插到数组的外面去（咋滴，你是想飞还是干啥，想插入到数组的外面去？），第二个条件是要插入的位置的前面的位置的值要比要插入的值大。刚才也分析过了，如果比要插入值小的话，就说明要插入值放在这个位置是正确的。（前面的位置比他小，后面的位置比他大）注意：此时要插入的值后面的那个值是和当前位置的值相同的。insertIndex是因为满足了insertVal < arr[insertIndex-1]（上一层循环的条件,因为insertIndex–同时由于数据右移了，所以，在本层循环应该是 insertVal< arr[insertIndex+1]）这个条件才来到这个位置的。所以说，如果不满足这个条件，insertVal就应该放在insertIndex上。

3. while循环里面是干啥？

   进入while循环就意味着满足 insertVal < arr[insertIndex-1]这个条件也就是说如果insertVal放在insertIndex这个位置是 arr[insertIndex] < arr[insertIndex-1]，后面比前面小，这不满足条件啊，所以说要移动位置继续向前探索！

插入排序的测试

测试环境及工具：我的电脑 Huawei MateBook 13+JDK1.8+Eclipse

测试手段：随机生成80000个[0,800000）的整数的数组进行排序，观察所花费的时间

测试代码：

public static void main(String[] args) {
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
//            arr[i] = (int) (Math.random()*80000);
            arr[i] = new Random().nextInt(800000);
        }
//        System.out.println(Arrays.toString(arr));
        long start_time = System.currentTimeMillis();
        insertSort(arr);
//        insertSortPlus(arr);
//        insertSortPlusPlus(arr);
//        insertSortSgg(arr);
        long end_time = System.currentTimeMillis();
//        System.out.println(Arrays.toString(arr));
        System.out.println("Time :"+(end_time-start_time)+"ms");

交换法

Time: 2531ms

Time: 2340ms

Time: 2376ms

移位法

Time: 1580ms

Time: 1580ms

Time: 1540ms

总结

和冒泡排序，选择排序比起来插入排序有一定的优势，毕竟是基本算法中既有稳定性，速度还可以的算法啦。移位法的速度比选择排序快一点，交换法虽然慢一点但是容易理解。这个移位法其实蛮容易理解的，可能是我没有画图，所以讲的不清楚吧，下次我把图补上(网上没找到合适的图)，应该就好多了吧。