插入排序实现原理：
例：现在有数组 int[] arr = {6,3,7,9,5,1,4,8}，从小到大排列
把arr数组假想成2个数组 一个有序数组(就是已经排好顺序的数组)，一个无序数组
有序数组为 arr[0]，arr[1],arr[2],arr[3]等后面的为无序数组，现在就是把无序数组的值插入到有序数组中。
先用变量保存有序数组的数字 int num = arr[0] ，定义下表index,index = 1；然后让后面的数字与他自己的前一个比较,现在就是arr[1]和arr[0]比较 ，下一轮为arr[2]和arr[1],arr[1]和arr[0]比较，以此类推
一个个的插入，首先把arr[1] 插入到有序数组中，现在的有序数组为{6}(假想的数组，无需创建新的数组)
判断 index>=0 && arr[1] < num(arr[0])
把6往后移动，新的数组为 {6,6,7,9,5,1,4,8}
然后改变arr[0]的值为刚才arr[1] (刚才的值为3) 的值即可
下面代码实现
public class InsertSort {
public static void main(String[] args) {
int[] arr = {6,3,7,9,5,1,4,8};
sort(arr);
System.out.println(Arrays.toString(arr));
}
//从小到大排序
public static void sort(int[] arr){
//从无序数组插入到有序数组，因为有序数组我们假想为当前的arr[0]，所以其后的数都为无序数组，所以从1开始遍历
for (int i = 1; i < arr.length; i++) {
//用临时变量保存需要插入的数据
int num = arr[i];
//有序数组的最后一位数的下标 因为第一次进来 所以为0 {6}
int index = i-1;
//关键判断,由于是从小到大排序，所以当前值如果小于有序列表的值,就进入循环移动位置,index一定得>=0
while (index>=0 && num<arr[index]) {
//把num插入到有序数组中，走完此步的数组为 {6,6,7,9,5,1,4,8};此时的index = 0
arr[index+1] = arr[index];
//走完此步 index = -1 退出循环
index--;
}
//现在的数组为 {6,6,7,9,5,1,4,8}
//我们把原来数组的arr[1]== 3 保存在临时变量num中,所以我们只要把现在数组的arr[0]的值变为3即可
//现在的index = -1 ; index + 1 = 0 ; 执行完下一句 数组为{3,6,7,9,5,1,4,8} ,以此内推，现在的有序列表{3,6} ,继续插入{7,9,5,1,4,8}
arr[index+1] = num;
}
}
}