将待排序的数组看成一个有序的数组和一个无序的数组，一般取数组的第一个元素为有序，后面其余的为无序，将无序的一个元素即排序数组的第2个元素，与有序数组的最后一个元素依次向前比较，找到正确的插入位置
以数组[220,52,43,510,12]为例
开 始：[220],52,43,510,12
第一轮：[52,220],43,510,12
第二轮：[43,52,220],510,12
第三轮：[43,52,220,510],12
第四轮：[12,43,52,220,510]
第一轮
public class InsertionAlgorithm { public static void main(String[] args) { int []arr={220,52,43,510,12}; //第一轮 有序{220} ，无序{52,43,510,10} //插入的数为52 int insertVal=arr[1]; //被插入的位置，即与他前面的一位比较，其下标为0 int index=1-1; //给insertVal找到插入的位置 // 说明 //1. Index >=0保证在给insertVal找插入位置,不越界 //2. insertVal < arr[Index]待插入的数，还没有找到插入位置 //3。就需要将arr[Index]后移一位 while(index>=0 && insertVal<arr[index]){ //将数组中的arr[index]向后移一位,即220 arr[index+1]=arr[index]; //让index向前移动，即继续向前比较，直到找到插入位置，跳出循环 index--; } //跳出循环,找到插入位置 //这里index+1是因为上面跳出循环时，index=-1 arr[index+1]=insertVal; System.out.println("第1轮结果"+ Arrays.toString(arr)); } }
结果：
整体代码
public class InsertionAlgorithm { public static void main(String[] args) { int[] arr = {220, 52, 43, 510, 12}; for (int i=1;i< arr.length;i++) { //第i轮 //插入的数为arr[i] int insertVal = arr[i]; //被插入的位置，即与他前面的一位比较，其下标为i-1 int index = i - 1; //给insertVal找到插入的位置 // 说明 //1. Index >=0保证在给insertVal找插入位置,不越界 //2. insertVal < arr[Index]待插入的数，还没有找到插入位置 //3。就需要将arr[Index]后移一位 while (index >= 0 && insertVal < arr[index]) { //将数组中的arr[index]向后移一位,即220 arr[index + 1] = arr[index]; //让index向前移动，即继续向前比较，直到找到插入位置，跳出循环 index--; } //跳出循环,找到插入位置 //这里index+1是因为上面跳出循环时，index=-1 arr[index + 1] = insertVal; System.out.println("第"+i+"轮结果" + Arrays.toString(arr)); } } }
结果：
原文：https://www.cnblogs.com/NiShilin/p/15032854.html