原理

數據分為 有序 | 無序兩個部分。以升序為例，遍歷數組，為當前值尋找在有序部分的合適位置插入并結束子循環(huán)，尋找的過程中將有序部分的值右移。

復雜度分析

平均時間復雜度為O(n^2)
時間復雜度最壞為O(n^2)
空間復雜度為 O(1)
穩(wěn)定

代碼實現

 public void sort(List<V> srcList, Comparator<V> comparator) {
        if (srcList == null || srcList.size() <= 2) {
            return;
        }
        for (int index = 0; index < srcList.size(); index++) {
            V element = srcList.get(index);
            V e2;
            int destIndex = index;
            //從有序部分最末向前遍歷，如果元素大于當前值element，將其后移一位，反之已找到合適位置，結束循環(huán)，插入element
            for (int j = index - 1; j >= 0 && comparator.compare(e2 = srcList.get(j), element) > 0; j--) {
                srcList.set(j + 1, e2);//后移一位
                destIndex = j;
            }
            if (destIndex != index) {
                srcList.set(destIndex, element);
            }
        }
    }