插入排序

思路

每次解决一个元素，把这个元素插入到后面曾经排好序的牌中的适合地位。

代码实现

public class InsertionSort {    private InsertionSort() {}    // 插入排序    public static <E extends Comparable<E>> void sort(E[] arr) {        for (int i = 0; i < arr.length; i++) {            for (int j = i; j - 1 >= 0; j--) {                if (arr[j].compareTo(arr[j - 1]) < 0) {                    swap(arr, j, j - 1);                } else {                    break;                }            }           /* for (int j = i; j - 1 >= 0 && arr[j].compareTo(arr[j - 1]) < 0 ; j--) {                swap(arr, j, j - 1);            }*/        }    }    // 替换    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[] arr = ArrayGenerator.generateRandomArray(n, n);               SortingHelper.sortTest("InsertionSort", arr);           }       }}

测试后果

插入排序是一个工夫复杂度为 O(n^2) 的排序算法，所以当 n 增大 10 倍的时候，排序所需工夫差不多差不多减少了 100 倍，运行后果如下所示：

插入排序的一个小优化

插入排序法中的每一次 swap(替换) 都须要三次操作，这里能够把这个替换操作优化成赋值操作。然而这个优化并不能扭转插入排序的工夫复杂度，它的工夫复杂度仍然是 O(n^2)。

 // 插入排序的优化public static <E extends Comparable<E>> void sort2(E[] arr) {    for (int i = 0; i < arr.length; 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;    }}

运行后果比照

能够看到，优化后的插入排序会比没有优化过的插入排序速度快一点，然而这个优化还是个常数级别的优化，并不能扭转算法的工夫复杂度，运行后果如下所示：

插入排序法的重要个性

插入排序法的内存循环有一个提前停止的机制，就是该元素比它后面元素还大的时候，那么循坏就会停止。所以，对于一个有序数组，插入排序的复杂度就是 O(n) 级别的。

所以对于一个近乎有序的数组，咱们能够应用插入排序法来进行排序。比照，抉择排序的算法复杂度永远是 O(n^2) 的。在一些高级排序的算法中，会利用插入排序的这一重要个性来进行优化。

比照测试

在不同数量级下，测试抉择排序和插入排序在随机数组和有序数组下的排序工夫。

public static void main(String[] args) {    int[] dataSize = {10000, 100000};    for (int n : dataSize) {        System.out.println("Random Array : ");        Integer[] arr = ArrayGenerator.generateRandomArray(n, n);        Integer[] arr2 = Arrays.copyOf(arr, arr.length);        SortingHelper.sortTest("SelectionSort", arr);        SortingHelper.sortTest("InsertionSort2", arr2);        System.out.println();        System.out.println("Ordered Array : ");        arr = ArrayGenerator.generateOrderedArray(n);        arr2 = Arrays.copyOf(arr, arr.length);        SortingHelper.sortTest("SelectionSort", arr);        SortingHelper.sortTest("InsertionSort2", arr2);        System.out.println();    }}

比照测试后果

能够看到，抉择排序的工夫复杂度始终是 O(n^2) 的，然而插入排序的工夫复杂度在有序数组中是 O(n) 级别的，具体后果如下所示：

_
以下是上述代码中用到的两个类:

ArrayGenerator

作用次要是生成随机的数组，具体如下所示：

public class ArrayGenerator {    private ArrayGenerator() {    }    /**     * 生成长度为 n 的有序数组     *     * @param n     * @return     */    public static Integer[] generateOrderedArray(int n) {        Integer[] arr = new Integer[n];        for (int i = 0; i < arr.length; i++) {            arr[i] = i;        }        return arr;    }    /**     * 生成长度为 n 的随机数组，每个数字的范畴是[0, bound)     *     * @param n     * @param bound     * @return     */    public static Integer[] generateRandomArray(int n, int bound) {        Integer[] arr = new Integer[n];        Random rnd = new Random();        for (int i = 0; i < n; i++) {            arr[i] = rnd.nextInt(bound);        }        return arr;    }}

SortingHelper

作用次要是测试各种排序算法的性能，具体如下所示：

public class SortingHelper {    private SortingHelper() {    }    /**     * 判断一个数组是否有序     *     * @param arr     * @param <E>     * @return     */    public static <E extends Comparable<E>> boolean isSorted(E[] arr) {        for (int i = 1; i < arr.length; i++) {            if (arr[i - 1].compareTo(arr[i]) > 0) {                return false;            }        }        return true;    }    /**     * 测试排序算法的性能     *     * @param sortName     * @param arr     * @param <E>     */    public static <E extends Comparable<E>> void sortTest(String sortName, E[] arr) {        long startTime = System.nanoTime();        if (sortName.equals("SelectionSort")) {            SelectionSort.sort(arr);        } else if (sortName.equals("InsertionSort")) {            InsertionSort.sort(arr);        } else if (sortName.equals("InsertionSort2")) {            InsertionSort.sort2(arr);        }        long endTime = System.nanoTime();        double time = (endTime - startTime) / 1000000000.0;        if (!SortingHelper.isSorted(arr)) {            throw new RuntimeException(sortName + " failed");        }        System.out.println(String.format("%s , n = %d : %f s", sortName, arr.length, time));    }}