維護(hù)已經(jīng)排好序的部分，插入需要重新維護(hù)（交換內(nèi)部位置）
如果是有序（和有序部分的隊(duì)尾比較），內(nèi)部只比較一次O(n)，適用于近乎有序的排序

/**
 * 插入排序 ：維護(hù)已經(jīng)排好序的部分，插入需要重新維護(hù)（交換內(nèi)部位置）
 * O(n2)
 * 如果是有序（和有序部分的隊(duì)尾比較），內(nèi)部只比較一次O(n)，適用于近乎有序的排序
 * 維護(hù)前半部分是有序的
 */
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;
                }
            }
        }
    }

    private static <E> void swap(E[] arr,int i,int j){
        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

優(yōu)化，不使用swap，減少賦值操作

    //優(yōu)化，保存初始值，使用移動(dòng)方式，減少賦值
    public static <E extends Comparable<E>> void sort2(E[] arr) {
        for (int i = 0; i< arr.length; i++)  {
            E t = arr[i];
            int j = i;
            for (;j-1>=0;j--) {
                if (t.compareTo(arr[j-1])<0){
                    arr[j] = arr[j-1]; // 向后移動(dòng)，和swap比減少了聲明和一次賦值操作
                } else {
                    break;
                }
            }
            arr[j] = t;
        }
    }