排序算法——插入排序

原理

数据分为 有序 | 无序两个部分。以升序为例，遍历数组，为当前值寻找在有序部分的合适位置插入并结束子循环，寻找的过程中将有序部分的值右移。

复杂度分析

平均时间复杂度为O(n^2)
时间复杂度最坏为O(n^2)
空间复杂度为 O(1)
稳定

代码实现

 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，将其后移一位，反之已找到合适位置，结束循环，插入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);
            }
        }
    }