排序基础(二)插入排序

最后更新于:2022-09-09 10:53:51

什么是插入排序

插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有 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)级别