算法描述

• 从第二个元素开始，依次插入其前有序数列（可以提前终止内循环的原因）的合适位置；

时间复杂度

• 最好情况，O(N)，数组近乎有序的情况下；
• 最坏情况，O(N^2)；
• 平均情况，O(N^2)；

算法实现

• 外层循环控制遍历的范围，一点点变大；
• 内层循环在范围里比较，和前面的元素比；
• 注意插入排序的内层循环的时候，是有机会提前终止的（比之前的元素大），不必将内层循环完整走一遍；
• 注意swap(Object[] arr, int j, int i) 中，数组的入参是用 Object[] 而不是 Compareble[]；

import util.SortTestHelper;

public class InsertionSort {

    private InsertionSort(){}

    public static void sort(Comparable[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j].compareTo(arr[j - 1]) < 0) {
                    swap(arr, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }

    private static void swap(Object[] arr, int j, int i) {
        Object temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    public static void main(String[] args) {
        int N = 10000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        SortTestHelper.testSort("_02.sortingbaisc._05.InsertionSort", arr);
    }

}

输出：

InsertionSort : 156ms