插入排序

维护已经排好序的部分，插入需要重新维护（交换内部位置）
如果是有序（和有序部分的队尾比较），内部只比较一次O(n)，适用于近乎有序的排序

/**
 * 插入排序 ：维护已经排好序的部分，插入需要重新维护（交换内部位置）
 * O(n²)
 * 如果是有序（和有序部分的队尾比较），内部只比较一次O(n)，适用于近乎有序的排序
 * 维护前半部分是有序的
 */
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;
    }
}

优化，不使用swap，减少赋值操作

    //优化，保存初始值，使用移动方式，减少赋值
    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]; // 向后移动，和swap比减少了声明和一次赋值操作
                } else {
                    break;
                }
            }
            arr[j] = t;
        }
    }