插入排序

插入排序原理：从左往右依次将数据插入到前面已排序好的数组中。

 

时间复杂度：最优O(n)，最坏O(n^2)，平均O(n^2)

 

数据已经正序排好的情况最优，倒序最坏 

 

public static <T extends Comparable<T>> int compare(T a, T b) {
    if (a == null){
        return b == null ? 0 : -1;
    }
    if (b == null){
        return 1;
    }
    return a.compareTo(b);
}

 

/**
 * @description 插入排序
 * @param data
 * @param offset
 * @param len
 */
private static <T extends Comparable<T>> void insertSort(T[] data, int offset, int len) {
    for (int j, i = offset + 1; i < len; ++i) {
        T tmp = data[i];
        //比当前数大，则往后移
        for (j = i; j > offset && compare(data[j - 1], tmp) > 0; --j) {
            data[j] = data[j-1];
        }
        //把当前数插入到有序数组中
        data[j] = tmp;
    }
}

/**
 * @description 插入排序
 * @param data
 */
public static <T extends Comparable<T>> void insertSort(T[] data) {
    if (data != null && data.length > 1){
        insertSort(data, 0, data.length);
    }
}