1.插入排序法

• arr[i…n)未排序, arr[0…i) 已排序 => 循环不变量 和选择排序法一致
• 进步：有序的集合+1，无序的集合-1
• 把arr[i]放到合适的位置

选择排序法与插入排序法的区别

插入排序的特性

• 内层循环能够提前终止
• 对于有序数组，插入排序不会真正去移动元素，只会比较与前面的元素比较一次，然后发现不需要移动。这种情况，时间复杂度就会由O(n^2)变成O(n)
• 对于基本有序的数组，使用插入排序是更好的选择，大部分内层循环都会直接跳过

插入排序的优化

• 不再依次向前面交换，而是使用临时变量缓存arr[i]的值，这样每一位都只移动一次；
• 时间复杂度没改变，是常数级别的优化。

优化后的结果

public class InsertSort {
    private InsertSort() {
    }
    private static <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            //将arr[i]插入到合适的位置
            for (int j = i; j - 1 >= 0 ; j--) {
                //依次当前值是否比前一个位置的值小，如果小就交换位置
                if (arr[j].compareTo(arr[j - 1]) < 0) {
                    swap(arr, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }
    private static <E extends Comparable<E>> void sort2(E[] arr) {
        //插入排序的优化
        // 临时变量缓存，就只用移动一次，不再依次向前交换了
        for (int i = 0; i < arr.length; i++) {
            //将arr[i]插入到合适的位置
            E temp = arr[i];
            int j;
            for (j = i; j - 1 >= 0 && temp.compareTo(arr[j - 1]) < 0; j--) {
                    arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }
    private static <E> void swap(E[] arr, int i, int j) {
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
        for (int n : dataSize) {
            Integer[] data = ArrayGenerator.generateRandomArray(n,n);
            Integer[] data2 = Arrays.copyOf(data, data.length);
            SortingHelper.sortTest(InsertSort.class, "sort", data);
            SortingHelper.sortTest(InsertSort.class, "sort2", data2);
        }
    }
}