维护已经排好序的部分，插入需要重新维护（交换内部位置）
如果是有序（和有序部分的队尾比较），内部只比较一次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;
}
}
