插入排序
工作原理：
从头开始遍历数组，如果发现当前项比前一项小，说明当前项应该插到前面，交换一下即可。
利用双层for循环，第一层是遍历整个数组，第二层负责遍历当前所遍历到的位置之前的数组。
/**
* @Author: 翰林猿
* @Description: 插入排序
**/
public class Insert {
public Insert() {
}
public static <E extends Comparable<E>> void InsertSort(E[] arr) {
for (int i = 0; i < arr.length; i++) { //遍历当前乱序的数组
for (int j = i; j >= 1; j--) { //从i开始去遍历当前位置i之前的元素，且j不能是第一项（找到合适的位置插入）
if (arr[j].compareTo(arr[j - 1]) < 0) { //如果当前项比前一项小，说明当前项应该插到前面
swap(j, j - 1, arr); //交换当前项和前一项，从而实现插入
} else {
break;
}
}
}
}
//由于多次使用swap进行交换导致性能变差，我们可以优化一下，直接找到应该插入的地址，然后将后面的值各自往后覆盖一位，最后将值插到该插入的地方即可。
public static <E extends Comparable<E>> void BetterInsertSort(E[] arr) {
for (int i = 0; i < arr.length; i++) { //遍历当前乱序的数组
E t = arr[i]; //用来暂存当前位置的值
int j; //提高作用域
//为什么for循环采用这种写法，因为如果在for里才用if判断compareTo的话j已经-1了
//如果if进不去j就会导致j多减几次，最后因为下标出错而覆盖出错。
for (j = i; j >= 1 && t.compareTo(arr[j - 1]) < 0; j--) { //如果暂存的值比前一项小，说明当前项应该插到前面
arr[j] = arr[j - 1]; //将前一项的值覆盖当前项（不需要交换，更快）
}
arr[j] = t; //把刚刚保存好的值放到最后j停下的位置即可
}
}
public static <E> void swap(int j, int beforej, E[] arr) { //一个简单的交换算法
E t = arr[j];
arr[j] = arr[beforej];
arr[beforej] = t;
}
public static void main(String[] args) {
Integer[] arr = {1, 8, 9, 7, 3, 5, 6};
Insert.BetterInsertSort(arr);
for (int it : arr) {
System.out.println(it);
}
}
}