6.插入排序-java

霍格沃兹测试学院校内交流
1

插入排序

有序度：比如说2、4、3、1、5、6这组数组的有序度是11，因为它有11个有序元素对，分别是(2,4)、(2,3)、(2,5) (2,6)、(4,5)、(4,6)、(3,5)、(3,6)、(1,5)、(1,6)、(5,6)。

逆序度：满有序度 - 有序度。

对于 6、5、4、3、2、1这组数据，它的有序度是0；对于1、2、3、4、5、6这组数据来说，它的有序度是n*(n-1)/2，这种完全有序的数组的有序度叫做满有序度。

移动次数 == 逆序度：n*(n-1)/2

import java.util.Arrays;

public class InsertionSort {
    public void insertionSort(int[] data) {
        if (data.length <= 1) {
            return;
        }
        for (int i = 1; i < data.length; i++) {
            int j = i - 1;
            int value = data[i];
            while (j >= 0 && data[j] > value) {
                data[j + 1] = data[j];
                --j;
            }
            data[j + 1] = value;

        }

    }

    public static void main(String[] args) {
        InsertionSort insertionSort = new InsertionSort();
        int[] data = new int[] { 5, 2, 1, 4, 10, 3, 6, 7 };
        insertionSort.insertionSort(data);
        int[] data2 = new int[] { 1, 2, 3, 4, 5, 6, 7, 10 };
        System.out.println(Arrays.equals(data, data2));

    }

}

空间复杂度：O(1)
时间复杂度：
最好：O(n)
最坏：O(n2)
平均：O(n*((1+2+3+…+n)/n)) = O(n2)

稳定：