插入排序

1 基本原理

遍历数组，将遍历的元素插入到已经排好序的数组里。比如6 3 2 7 首先我们将a[0]当成已经有序的数组，然后将a[1]插入到有序的数组里，变为3 6 2 7，这时有序数组为a[0] a[1]，然后将a[2]插入到已经有序的数组里，变为 2 3 6 7 ,然后继续...

2 具体实现

public static void InsertSort(int[] arr){
        int len = arr.length;
        for (int i = 1; i < len; i++) {
      //将小的元素持续交换到合适的位置
            for(int j = i; j >= 1 && SortUtil.less(arr,j,j-1);j--) {
                SortUtil.swap(arr,j,j-1);
            }
        }
    }

如果在内循环中，将元素后移而不是交换，那么我们可以大幅降低元素交换次数，从而提高性能。

 public static void InsertSort(int[] arr){
        int len = arr.length;
        for (int i = 1; i < len; i++) {
//记住当前元素
            int cur = arr[i];
            int j;
            for(j = i; (cur < arr[j-1]) && j > 0;j--){
                 arr[j] = arr[j-1];
            }
//将元素放到合适的位置
            arr[j] = cur;
        }
    }

3 算法分析

时间复杂度基本是O(n)~O(N^2)，空间复杂度O(1),属于稳定排序