JAVA 插入排序算法(详细实现过程介绍)_综合

场景：
对数组int []arr={ 101, 34, 119, 1}，使用插入排序方式实现从小到大排序。

思路分析：
4个数，外层循环需要排序三轮，即：循环从1开始，循环次数为数组的长度

1、第一轮排序的结果为：34,101,119, 1
1）设定下标为0的第一个数不动，下标为1的数为要插入的数 insertVal,该数的前一个数的下标preIndex为0即: 1-1
2）使用while循环，循环条件为：preIndex>=0 && insertVal<insertVal的前一个数
   如果满足while循环的条件，此时arr[preIndex]=101，arr[preIndex+1]=34，就将前一个数的值设置为下一个数的值，
   即：arr[preIndex+1] = arr[preIndex],此时，数组中的元素顺序为：101, 101, 119, 1
并将preIndex--，此时preIndex=-1，不再满足while循环的preIndex>=0条件，退出循环。
   如果不满足while循环的条件，就设置 arr[preIndex+1]=insertVal，此时，数组中的元素顺序为：34,101,119, 1
如果insertVal的下标与preIndex+1的值相等，则不需要设置arr[preIndex+1]=insertVal

int insertVal = arr[1];
int preIndex = 0;
while(preIndex>=0 && insertVal<arr[preIndex]){arr[preIndex+1] = arr[preIndex];preIndex--;
}
if(preIndex+1 !=1){arr[preIndex+1]=insertVal;
}

2、第二轮排序的结果为：34,101,119, 1
1）下标为2的数为要插入的数 insertVal,该数的前一个数的下标preIndex为1即: 2-1
2）使用while循环，循环条件为：preIndex>=0 && insertVal<insertVal的前一个数
此时insertVal>insertVal的前一个数,不满足while循环的 insertVal<insertVal条件，退出循环。
因为此时，insertVal的下标为2，preIndex+1=2，所以不需要设置arr[preIndex+1]=insertVal，即要插入的数位置未发生变化，
此时，数组中的元素顺序仍为：34,101,119, 1


int insertVal = arr[2];
int preIndex = 1;
while(preIndex>=0 && insertVal<arr[preIndex]){arr[preIndex+1] = arr[preIndex];preIndex--;
}
if(preIndex+1 !=2){arr[preIndex+1]=insertVal;
}

3、第三轮排序的结果为： 1,34,101,119
1）下标为3的数为要插入的数 insertVal,该数的前一个数的下标preIndex为2即: 3-1
2）使用while循环，循环条件为：preIndex>=0 && insertVal<insertVal的前一个数
如果满足while循环的条件，此时arr[preIndex]=119，arr[preIndex+1]=1，将前一个数的值设置为下一个数的值。
即：arr[preIndex+1] = arr[preIndex],此时，数组中的元素顺序为：34,101,119,119
并将preIndex--，此时preIndex=2-1=1，仍满足while循环的条件。

   继续循环，被插入的数为1，仍然比arr[preIndex]=101小，此时arr[preIndex]=101，arr[preIndex+1]=119，
   设置：arr[preIndex+1] = arr[preIndex],此时，数组中的元素顺序为：34,101,101,119
并将preIndex--，此时preIndex=1-1=0，仍满足while循环的条件。

   继续循环，被插入的数为1，仍然比arr[preIndex]=34小，此时arr[preIndex]=34，arr[preIndex+1]=101，
   设置：arr[preIndex+1] = arr[preIndex],此时，数组中的元素顺序为：34,34,101,119
并将preIndex--，此时preIndex=-1，不再满足while循环的preIndex>=0条件，退出循环。

如果不满足while循环的条件，就设置 arr[preIndex+1]=insertVal，此时，数组中的元素顺序为：1,34,101,119
如果insertVal的下标与preIndex+1的值相等，则不需要设置arr[preIndex+1]=insertVal

int insertVal = arr[3];
int preIndex = 2;
while(preIndex>=0 && insertVal<arr[preIndex]){arr[preIndex+1] = arr[preIndex];preIndex--;
}
if(preIndex+1 !=3){arr[preIndex+1]=insertVal;
}

最终代码为：

int [] arr = {101, 34, 119, 1};
for(int i=1;i<=arr.lenght()-1;i++){int insertVal = arr[i];int preIndex = i-1;while(preIndex>=0 && insertVal<arr[preIndex]){arr[preIndex+1] = arr[preIndex];preIndex--;}if(preIndex+1!=i){arr[preIndex+1]=insertVal;}}

输出结果：
第1轮排序的结果为:[34, 101, 119, 1]
第2轮排序的结果为:[34, 101, 119, 1]
第3轮排序的结果为:[1, 34, 101, 119]