什么是插入排序

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有 1 个元素，也就是第一个元素（默认它有序）。
比较是从有序序列的末尾开始，也就是把待插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面。
否则一直往前找直到找到它该插入的位置。如果遇见一个与插入元素相等的，那么把待插入的元素放在相等元素的后面。
所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序仍是排好序后的顺序，所以插入排序是稳定的。

代码

public class InsertingSort {

    private InsertingSort() {}

    public static > void sort(T[] arr) {
        for (int i = 0; i < arr.length; i++) {
            T t = arr[i];
            int j;
            for (j = i; j - 1 >= 0 && t.compareTo(arr[j - 1]) == -1; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = t;
        }
    }
}

测试

    public static void main(String[] args) {
        int[] dataSize = {10000, 100000};
        for (int n : dataSize) {
            Integer[] datas = ArrayGenerator.generatorRandomArray(n, n);
            SortHelper.sortTest("InsertingSort", datas);
        }
    }

结果

InsertingSort,n = 10000 : 0.120011 s
InsertingSort,n = 100000 : 9.492279 s

从结果看，数据增加了10倍，时间性能增加了100倍，由此可以得出选择排序的时间复杂度为O(n)²级别的

插入排序的重要特性

插入排序有两个for循环，但是第二个for循环是有提前结束的标志的，t.compareTo(arr[j - 1]) == -1，也就是说，在一个已经排序完成的数组来进行插入排序，那么插入排序就会变成一个O(n)级别的算法。但是整体来看，依然是O(n)²级别的

测试

 public static void main(String[] args) {
        int[] dataSize = {10000, 100000};
        for (int n : dataSize) {
            Integer[] datas = ArrayGenerator.generatorOrderArray(n);
            SortHelper.sortTest("InsertingSort", datas);
        }
    }

结果

InsertingSort,n = 10000 : 0.000964 s
InsertingSort,n = 100000 : 0.004133 s

从结果看，数据增加了10倍，时间性能增加了0.5倍左右，由此可以得出选择排序的时间复杂度为O(n)级别的

与选择排序的对比

    public static void main(String[] args) {
        int[] dataSize = {10000, 100000};
        for (int n : dataSize) {
            System.out.println("无序数组:");
            Integer[] arr = ArrayGenerator.generatorRandomArray(n, n);
            Integer[] arr2 = Arrays.copyOf(arr, arr.length);
            SortHelper.sortTest("InsertingSort", arr);
            SortHelper.sortTest("SelectionSort", arr2);
            System.out.println();
            System.out.println("有序数组:");

            arr = ArrayGenerator.generatorOrderArray(n);
            arr2 = Arrays.copyOf(arr, arr.length);

            SortHelper.sortTest("InsertingSort", arr);
            SortHelper.sortTest("SelectionSort", arr2);
            System.out.println();
        }
    }

结果

无序数组:
InsertingSort,n = 10000 : 0.131883 s
SelectionSort,n = 10000 : 0.124702 s

有序数组:
InsertingSort,n = 10000 : 0.000211 s
SelectionSort,n = 10000 : 0.122985 s

无序数组:
InsertingSort,n = 100000 : 9.266880 s
SelectionSort,n = 100000 : 14.056764 s

有序数组:
InsertingSort,n = 100000 : 0.000509 s
SelectionSort,n = 100000 : 13.253081 s

可以看出，对于无序数组来说，两个方法的结果是相差不大的，两个都是O(n)²级别的算法，但是对于有序数组，差别却相当大，选择排序依然是O(n)²级别，而插入排序则变成了O(n)级别