1.什么是插入排序

将一个记录插入到已经排好序的有序表中, 从而得到一个新的,记录数增1的有序表

2.实现思路：

1.从数组的第二个数据开始往前比较，即一开始用第二个数和他前面的一个比较，如果 符合条件（比前面的大或者小，自定义），则让他们交换位置。

2.然后再用第三个数和第二个比较，符合则交换，但是此处还得继续往前比较，比如有 5个数8，15，20，45, 17,17比45小，需要交换，但是17也比20小，也要交换，当不需 要和15交换以后，说明也不需要和15前面的数据比较了，肯定不需要交换，因为前 面的数据都是有序的。

3.重复步骤二，一直到数据全都排完。

3.动图演示：

插入排序.gif

4.代码演示：

 public static void sort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            while (j > 0){
                if (arr[j] < arr[j-1]){
                    int temp ;
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                    //System.out.println(Arrays.toString(arr));
                    j--;
                }else {
                    break;
                }
            }
        }
        //System.out.println(Arrays.toString(arr));
    }

5.时间复杂度

在插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较N- 1次，时间复杂度为O(N)

最坏的情况是待排序数组是逆序的，此时需要比较次数最多，总次数记为：1+2+3+…+N-1，所以，插入排序最坏情况下的时间复杂度为O(N²)