**插入排序原理：**存在一个数字arr，用i遍历数组。首先，令key=arr[i]，取出第i个值，然后让他跟前面的i个数比较，找到arr[p]<key 并且arr[p+1]>key。将第p+1到第i-1个数向右侧移动，此时arr[p+1]是空出来的，然后将key放在这个地方，数组0到i就是有序的了，然后向后移动，完成遍历。 代码：
public static int[] InsertionSort(int [] arr){ for (int i = 1; i <arr.length ; i++) {// 从第二个数开始遍历一边数组 int key=arr[i]; int j=i-1; while (j>=0&&key<arr[j]){//判断没有越界，将数插入 arr[j+1]=arr[j]; j--; } arr[j+1]=key; } return arr; }