插入排序

概述

　　最近在学习算法，面试时候问了我快速排序，当场懵逼了，竟然没有听说过，我支支吾吾了半天然后告诉面试官，我TM没听说过，然后面试官用一种看智障的眼神结束了面试（以上纯属虚构，哈哈），本来以为排序算法也就什么冒泡排序，快速排序什么的，今天自己一看，我姹，竟然那么多种排序算法，没办法了，只能一个一个的看咯。

核心思想

　　其实核心思想很简单，就是把一个数组中的数据分成两个部分，第一部分是排好序的，第二部分是还没有排序的，然后遍历第二部分的数据，查找这个元素应该在第一个排好序的部分的什么位置，然后插入这个地方，之后把第一部分插入元素之后的部分向后移动。说着一大段，有些麻烦，下面通过一个例子讲解一下。

举例： 3,4,1,5,2,6

要求：使用插入排序算法进行排序（从小到大）

实现过程：

第一步：假设排好序的部分就是3,未排序部分为4，1，5, 2, 6

第二步：遍历第二步分数据和第一部分数据（由于现在只有一个，直接比较了），发现4>3，继续下一个，发现3>1，那1应该在3的前面，把1插入到3的位置，之后元素3和4向后移动，注意：不要动5,2,6的位置

第三步：经过第二步处理之后，排好序的部分为1,3,4 未排序的部分为5, 2，6，重复第二步

总结：简单来说，就是把未排序的数据元素寻找在排好序的数据元素中的位置，然后插入进入，之后排好序的数据元素向后移动（注意：这里是从插入的位置向后移动，并不是全部排好序的部分）

改进版本

　　在上面的过程中，排好序的数组也需要一个一个遍历，最终找到元素需要插入的位置，这样时间复杂度太高，可以使用二分法查找，因为这一部分数组本身是有序的，使用二分法查找速度快很多。

举例：1,5,6,8,10,9

假设标绿的部分是已经排好序的，如果按照上面遍历的方法，需要查5次才知道9应该插入8和10之间，如果使用二分法查找，如下：

第一步：计算中间值（0 + 4）/ 2 = 2，发现数组中下标为2的位置元素为 6 ，而 6 < 9,继续

第二步：计算中间值（2 + 4）/ 2 = 3，发现数组中下标为3的位置元素为8，而 8 < 9，继续

第三步：计算中间值（3 + 4）/ 2 = 3.5,把3.5取整为4，之后发现下标为4的元素为10，而 10 > 9，ok，发现9应该插入10的位置，而10应该向后移动

整个过程只需要查找3次，所以快非常多。

其实，遍历的时间复杂度为O(n)，而二分法查找时间复杂度为O(log(n))

代码实现

package sort;

/**
 * @author: steve
 * @date: 2020/7/6 16:44
 * @description: 插入排序
 */
public class InsertSort {

    public static int array[] = {72, 6, 57, 88, 60, 42, 83, 73, 48, 8, 1};

    /***
     *@Description 插入排序
     *@Param []
     *@Return void
     *@Author steve
     */
    public static void insertSort() {
        //排好序的位置
        int flag = 1;
        int temp = 0;
        //外层循环控制未排序的部分
        for (int j = 1; j < array.length; j++) {
            //内层循环处理排过序的部分
            for (int i = 0; i < flag; i++) {
                if (array[i] > array[j]) {
                    temp = array[j];
                    System.arraycopy(array, i, array, i + 1, j - i);
                    array[i] = temp;
                    flag = j + 1;
                }
            }
        }
    }

    /***
     *@Description 二分插入排序
     *@Param []
     *@Return void
     *@Author steve
     */
    public static void bisectionInsertSort() {
        int flag = 0;
        int temp;
        for (int i = flag + 1; i < array.length; i++) {
            int result = bisectionSearch(flag, array[i]);
            temp = array[i];
            System.arraycopy(array, result, array, result + 1, i - result);
            array[result] = temp;
            flag = flag + 1;

        }
    }

    /***
     *@Description 二分查找
     *@Param [flag:排好序的位置, num:待排序数]
     *@Return int
     *@Author steve
     */
    public static int bisectionSearch(int flag, int num) {

        int start = 0;
        int end = flag;
        int mid;
        //通过while循环，最后一定可以end-start<=1,也就是说要插入的元素一定在start左边，或者等于start，或者在start和end之间
        while (end >= start) {
            //由于这里mid的计算方式，导致要插入的元素不可能存在end-start=1,且end=要插入的元素的情况
            mid = (start + end) / 2;
            if (array[mid] > num) {
                end = mid - 1;
            } else if (array[mid] <= num) {
                start = mid + 1;
            }
        }
        return start;
    }

    public static void main(String[] args) {
//        insertSort();
        bisectionInsertSort();
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
}

上面的写法可能有的胖友对arraycopy比较好奇，大家可以自己写个demo试一下这个方法有什么用，我也是参考java8中ArrayList的sort方法写的，他就是用这个函数搞的。至于这个函数的性能和普通的遍历的性能对比，我也不太清楚，不过这个方法是一个native方法，性能应该还可以。

总结

　　写这种算法，思路一定要清晰，通过实验是不管用的，思路清晰了，很快就可以写出来，不然写的一定很复杂。