一.插入排序的思想
思想：将需要进行排序的数看作两部分：有序数列和无序数列，通常以第一个数为有序数列，从第二个数开始到最后的数看做无序数列，将无序数列中的数逐个添加到有序数列中，直至整个数列为有序状态。
二.方式一
将需要插入的数逐个与有序数列中的数进行比较，若不满足有序状态则进行交换，交换完之后再进行比较，继续交换；若满足，则不交换。整体效果有点类似向前的冒泡排序。
例：8,2,4,9,3,6,5,1进行从小到大的排序
将8看作有序数列，将2,4,9,3,6,5,1看作无序数列，分别将2,4,9,3,6,5,1与8作比较，并交换位置
8,2,4,9,3,6,5,1 2比8小，交换位置
2,8,4,9,3,6,5,1 4比8小，交换位置
2,4,8,9,3,6,5,1 9经过比较后不用换位置，3开始插入，3比9小，交换
2,4,8,3,9,6,5,1 3比8还小，继续交换
2,4,3,8,9,6,5,1 3比4还小，继续交换
2,3,4,8,9,6,5,1 看看过程，是不是和冒泡排序有点像，后面类似就不继续举例了。
代码实现：
public static void sort(int[] array){ //从数组的第一位视为有序数列 for(int i =1 ; i < array.length;i++){ //将带插入的数据与有序数列尾部进行逐一比较，实施交换操作 for(int j = i ;j > 0 ;j--){ if(array[j] < array[j-1]){ swap(array,j-1,j); } } } } //交换 public static void swap(int[] arr,int a, int b){ int temp = arr[b]; arr[b] = arr[a] arr[b] = temp }方式二：
将要插入的数字的位置定位出来，将其插入，并将要排在插入数字后面的数字往后移动
例：3,2,9,0，首先将2与3进行对比，发现2小于3，将3往后移动，将2插入首位
代码实现：
public static void sort(int[] array){ int[] res = new int[1]; res[0] = array[0]; for(int i = 1;i <array.length;i++){ //使用递归调用，注意要更新维护res，即每次返回的新数组 res= res(res,array[i]); } } //每次将要插入的元素ele插入数组中，并返回插入后的新数组 public static int[] res(int[] intArr,int ele){ int findPos = findPos(intArr,ele); int[] temp = new int[intArr.length+1]; for(int m =0;m <=findPos-1;m++ ){ temp[m] = intArr[m]; } for(int n =findPos+1;n <=temp.length;n++ ){ temp[n] = intArr[n-1]; } temp[findPos] = ele; return temp; } //找到新插入的数字要插入的位置 public static void findPos(int[] arr,int num){ int temp = arr.length; for(int j = arr.length-1;j>=0;j--){ //注意插入元素位置为最前面这种情况 if(num < arr[0]){ return 0; } if(num < arr[j] && num > arr[j-1]){ temp = j } } return temp; }
