同学说有更多细节的排序算法插入排序

这是排序算法学习的第三章「插入排序算法」，排序算法作为实用且面试常考的算法，虽然各大编程语言都有其相关的API实现。但是通过学习各种排序算法来训练编码能力，锻炼算法思维，入门算法~

目前为止，我们已经学习了

两者排序算法的优劣其实都差不太多，都是时间复杂度为O(N2)O(N^2)O(N2),空间复杂度为O(1)O(1)O(1)。最为不同的区别在于对于稳定性上：

今天我们就来学习第三种排序算法：插入排序

下面是各大排序算法的时间复杂度和空间复杂度，以及稳定性

算法描述

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

对于一个待排序的数组（升序），从第二个元素开始（称为插入对象元素），比较它与之前的元素（称为比较对象元素，有序），当插入元素小于比较元素时，比较元素「后移」，继续往前比较，直到「大于等于」比较对象，此时将插入对象元素插入到该比较对象元素之后。重复这个过程直到最后一个元素作为对象完成插入操作。

根据描述，我们可以很自然的发现此排序的操作最主要的操作就是「插入」。选定一个元素与之前的元素进行比较当符合要求时进行插入操作。

稳定性

插入排序的核心操作就是与前面的元素进行比较，找到符合的位置进行插入。所以并不会改变过数组中的相等元素的相对位置。所以是保证其「稳定性」的。

代码实现

    public static void insertSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i = 0; j--) {
                //元素往后移
                if (target < arr[j]) arr[j + 1] = arr[j];
                    //此时target要大于等于arr[j] 说明target要插入j+1位置
                else break;
            }
            // j变动表示发生了移动，此时的插入对象数字 ≥ j位置的数字，故插入位置为j + 1
            if (j != i - 1) arr[j + 1] = target;
        }
    }

代码优化

通过算法描述我们可以知道插入排序算法的核心（升序）：在一个已经「有序」的数组中，找到「插入对象元素」的位置。其实这个过程是可以使用一个算法来优化的。它就是「二分查找」，找到数组中「大于等于」插入元素的位置，就是要插入的位置。（这里就不细讲二分了，挖坑）。找到要插入的位置之后，把前面的元素都向后移动，然后进行插入即可。

同时还存在当前「插入对象」大于前一个对象时，因为前面的数组已经有序，所以当前元素是不需要排序了。可以跳过。

    public static void insertSortOpt(int[] arr) {

        int n = arr.length;

        for (int i = 1; i < n; ++i) {

            //如果当前插入对象大于前一个对象，无需插入（因为[0,i-1]已经有序 剪枝）

            if (arr[i - 1]