4.插入排序（稳定排序）

最坏、平均时间复杂度：O(n2)
最好时间复杂度：O(n)
空间复杂度：O(1)

for (int i = 1; i < array.length; i++) {
    int cur = i;
    while (cur > 0 && cmp(cur, cur - 1) < 0) {
        //交换元素
        swap(cur, cur - 1);
        cur--;
    }
}

逆序对：

for (int i = 1; i < array.length; i++) {
            int cur = i;
            E temp = array[cur];
            while (cur > 0 && cmp(cur, cur - 1) < 0) {
                array[cur] = array[cur - 1];
                cur--;
            }
            array[cur] = temp;
        }

二分搜索优化插入排序

public void sort() {
        for (int i = 1; i < array.length; i++) {
            E value = array[i];
            //挪动范围
            int insertIndex = search(i);
            for (int j = i; j > insertIndex; j--) {
                array[j] = array[j-1];
            }
            array[i] = value;
        }
    }
    public int search(int index) {
        int begin = 0;
        int end = array.length;
        while (begin < end) {
            int mid = (begin + end) >> 1;
            if (cmp(array[index], array[mid]) < 0) {
                end = mid;
            }else {
                begin = mid + 1;
            }
        }
        return begin;
    }
//注意 使用二分搜索后，只是减少了比较次数，但是插入排序的平均复杂度任然是O(n^2)