排序算法之插入排序(带优化)

插入排序

什么是插入排序？

插入排序的原理： 一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法
。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增 1
的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 。

选择排序的基本思想是： 将未排序的元素一个一个地插入到有序的集合中，插入时把所有有序集合从后向前扫一遍，找到合适的位置插入。

案例演示

解释：
如上图，每次按顺序拿出一个数据与其前面的数据依次进行比较，直到找到他应该放的位置，然后放置下一个数据，当一边过去，数组就是一个有序数组了。

时间复杂度：

从上图可知：1+2+3+…+（n-1）=n(n-1)/2
所以时间复杂度为：O(n²)。

算法实现

我们从第二个数据开始，每次获取一个数据，记录下他的值insertVal，如果前一个位置有值且它的值比前一个位置的值小，让他前一个位置的值后移一位，再次进行比较，直到条件不满足，此时就找到了需要插入的位置，将这个数据insertVal放在这个位置，当所有元素遍历完成，此数组即为有序数组。

代码实现(双层for)

 public static void insert(int[] arr) {
        //定义临时变量
        int insertVal, insertIndex;
        for (int i = 1; i < arr.length; i++) {
            insertVal = arr[i];
            insertIndex = i - 1;
            for (int j = 0; j <= i; j++) {
                if (insertIndex >= 0 && arr[insertIndex] > insertVal) {
                    arr[insertIndex + 1] = arr[insertIndex];
                    insertIndex--;
                } else {
                        arr[insertIndex + 1] = insertVal;
                        break;
                }
            }
        }
    }

结果：
排序前：[114, 34, 119, 1]
排序后：[1, 34, 114, 119]

代码优化

如果我们比较发现这个数当前的位置就是正确位置，不满足if条件在else中就会进行赋值操作，这一步是不是很多余，我们只需要判断一下，insertIndex + 1 != i，这个时候我们在赋值，如果相等证明就是在正确位置。

优化后代码(双层for)

//插入排序,使用双层for
    public static void insert(int[] arr) {
        //定义临时变量
        int insertVal, insertIndex;
        for (int i = 1; i < arr.length; i++) {
            insertVal = arr[i];
            insertIndex = i - 1;
            for (int j = 0; j <= i; j++) {
                if (insertIndex >= 0 && arr[insertIndex] > insertVal) {
                    arr[insertIndex + 1] = arr[insertIndex];
                    insertIndex--;
                } else {
                    if (insertIndex + 1 != i) {//因为当insertIndex+1 == i 的时候原位置就是正确位置，不需要在进行赋值
                        arr[insertIndex + 1] = insertVal;
                        break;
                    }
                }
            }
        }
    }

优化后代码(for+while)

 //插入排序，使用for嵌套while
    public static void insert2(int[] arr) {
        //定义临时变量
        int insertVal, insertIndex;
        for (int i = 1; i < arr.length; i++) {
            insertVal = arr[i];//待插入的数字
            insertIndex = i - 1;//待插入数字前一个
            //while进行判断，看是否找到需要插入的位置
            /**
             * 说明：
             * insertIndex >= 0 保证不越界
             * arr[insertIndex] > insertVal 证明insertIndex位置的数还是大于待插入的数，还得往前面找
             */
            while (insertIndex >= 0 && arr[insertIndex] > insertVal) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            //当退出while循环的时候，说明找到位置，insertIndex+1
            if (insertIndex + 1 != i) {//因为当insertIndex+1 == i 的时候原位置就是正确位置，不需要在进行赋值
                arr[insertIndex + 1] = insertVal;
            }
        }
    }

源代码：

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int arr[] = {114, 34, 119, 1};
//        int[] arr = new int[800000];
//        for (int i=0;i<800000;i++){
//            arr[i] = (int)(Math.random()*8000000);
//        }
        System.out.println("排序前：" + Arrays.toString(arr));
//        long l1 = System.currentTimeMillis();
        insert(arr);
//        long l2 = System.currentTimeMillis();
//        System.out.println((l2-l1)/1000+"秒");
        System.out.println("排序后：" + Arrays.toString(arr));
    }

    //插入排序,使用双层for
    public static void insert(int[] arr) {
        //定义临时变量
        int insertVal, insertIndex;
        for (int i = 1; i < arr.length; i++) {
            insertVal = arr[i];
            insertIndex = i - 1;
            for (int j = 0; j <= i; j++) {
                if (insertIndex >= 0 && arr[insertIndex] > insertVal) {
                    arr[insertIndex + 1] = arr[insertIndex];
                    insertIndex--;
                } else {
                    if (insertIndex + 1 != i) {//因为当insertIndex+1 == i 的时候原位置就是正确位置，不需要在进行赋值
                        arr[insertIndex + 1] = insertVal;
                        break;
                    }
                }
            }
        }
    }

    //插入排序，使用for嵌套while
    public static void insert2(int[] arr) {
        //定义临时变量
        int insertVal, insertIndex;
        for (int i = 1; i < arr.length; i++) {
            insertVal = arr[i];//待插入的数字
            insertIndex = i - 1;//待插入数字前一个
            //while进行判断，看是否找到需要插入的位置
            /**
             * 说明：
             * insertIndex >= 0 保证不越界
             * arr[insertIndex] > insertVal 证明insertIndex位置的数还是大于待插入的数，还得往前面找
             */
            while (insertIndex >= 0 && arr[insertIndex] > insertVal) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            //当退出while循环的时候，说明找到位置，insertIndex+1
            if (insertIndex + 1 != i) {//因为当insertIndex+1 == i 的时候原位置就是正确位置，不需要在进行赋值
                arr[insertIndex + 1] = insertVal;
            }
        }
    }
}