public static void insertionSort(int[] ints) {
    for (int i = 0; i < ints.length; i++) {

        for (int j = i; j > 0; j--) {

            if (ints[j] < ints[j - 1]) {
                exch(ints, j, j - 1);

            } else {
                break;
            }
        }
    }
}

Insertion Sort

• 适用于小数组,数组已排好序或接近于排好序速度将会非常快

• 复杂度：O(n^2) - O(n) - O(n^2) - O(1)[平均 - 最好 - 最坏 - 空间复杂度]

public static void insertSort(int[] a) {
    if (a == null || a.length <= 1) {
        return;
    }
    for (int i = 1; i < a.length; i++) {
        int temp = a[i];
        int j = i - 1;
        while (0 <= j && temp < a[j]) {
            a[j + 1] = a[j];
            j -= 1;
        } 
        a[j + 1] = temp;
    }
}