插入排序
思路
1、把所有的元素分为两组，已经排序和未排序。
2、找到未排序的组中的第一个元素，向已经排序的组中进行插入。
3、倒序遍历已经排序的元素，依次和待插入元素进行比较，直到找到一个元素小于或等于待插入元素，那么就把待插入元素放到这个位 置，其他元素向后移动一位。
原始数据
第一趟排序
我们将数组的第一个数字划分到已经排序的组，把剩下的数字划分到未排序的组。
待插入数字：6
待插入位置索引假定为：0 （也就是数字3的索引）
第一次比较：待插入数字（6） > 待插入索引位置的数字（3）。
找到插入位置：索引为0。
由于插入位置索引值+1 = 待插入位置，说明没有移动，无需交换
将6划分到已经排序的组
第二趟排序
待插入数字：4
待插入位置索引假定为：1 （也就是数字6的索引）
第一次比较：4 < 6, 将数字6后移。此时，待插入索引位置：0
第二次比较： 4 > 3 。
找到插入位置：索引0。
由于插入位置索引值+1 != 待插入位置，说明有移动，需要交换
将待插入数字（4）放在（插入位置+1）的地方 
第三趟排序
待插入数字：1
待插入位置索引假定为：2
第一次比较：
1 < 6, 将6后移, 待插入索引：1
第二次比较：
1 < 4，将4后移。 待插入索引：0
第三次比较：
1 < 3, 将3后移。待插入索引：-1
由于待插入索引为 -1，所以无需再操作
由于插入位置索引值+1 != 待插入位置，说明有移动，需要交换
第四趟排序
待插入数字：2
待插入位置索引假定为：3
第一次比较：
2 < 6。 6 后移
第二次比较：
2 < 4, 4后移
2 < 3, 3后移
2 > 1, 找到插入位置：索引0
由于插入位置索引值+1 != 待插入位置，说明有移动，需要交换
第一趟排序代码
public class InsertionSort {
public static void main(String[] args) {
int[] value = {3,6,4,1,2};
new InsertionSort().sort(value);
for (int i : value) {
System.out.print(i + ",");
}
}
public void sort(int[] value){
int insertValue = value[1];
int insertIndex = 0;
//退出循环时说明找到插入的位置
while (insertIndex >= 0 && insertValue < value[insertIndex]) {
value[insertIndex + 1] = value[insertIndex];
insertIndex--;
}
//判断是否需要挪动位置
if (insertIndex + 1 != 1){
value[insertIndex + 1] = insertValue;
}
}
}
运行结果：3,6,4,1,2,
第二趟排序代码
public class InsertionSort {
public static void main(String[] args) {
int[] value = {3,6,4,1,2};
new InsertionSort().sort(value);
for (int i : value) {
System.out.print(i + ",");
}
}
public void sort(int[] value){
int insertValue = value[2]; //待插入数字
int insertIndex = 1; //待插入的地方的索引
//退出循环时说明找到插入的位置
while (insertIndex >= 0 && insertValue < value[insertIndex]) {
value[insertIndex + 1] = value[insertIndex]; //每次将待插入位置的数字向后挪动一位。
insertIndex--;
}
if (insertIndex + 1 != 2){
value[insertIndex + 1] = insertValue;
}
}
}
运行结果：3,4,6,1,2,
第三趟排序代码
public class InsertionSort {
public static void main(String[] args) {
int[] value = {3,4,6,1,2};
new InsertionSort().sort(value);
for (int i : value) {
System.out.print(i + ",");
}
}
public void sort(int[] value){
int insertValue = value[3];
int insertIndex = 2;
//退出循环时说明找到插入的位置
while (insertIndex >= 0 && insertValue < value[insertIndex]) {
value[insertIndex + 1] = value[insertIndex];
insertIndex--;
}
if (insertIndex + 1 != 3){
value[insertIndex + 1] = insertValue;
}
}
}
运行结果：1,3,4,6,2,
第四趟排序代码
public class InsertionSort {
public static void main(String[] args) {
int[] value = {1,3,4,6,2};
new InsertionSort().sort(value);
for (int i : value) {
System.out.print(i + ",");
}
}
public void sort(int[] value){
int insertValue = value[4];
int insertIndex = 3;
//退出循环时说明找到插入的位置
while (insertIndex >= 0 && insertValue < value[insertIndex]) {
value[insertIndex + 1] = value[insertIndex];
insertIndex--;
}
if (insertIndex + 1 != 4){
value[insertIndex + 1] = insertValue;
}
}
}
运行结果：1,2,3,4,6,
最终代码
外层循环控制趟数，也就是（数组的长度-1）次
外层循环的值，也就是待插入数字的索引值
外层循环的值-1 就是待插入索引的值
public class InsertionSort {
public static void main(String[] args) {
int[] value = {1,3,4,6,2};
new InsertionSort().sort(value);
System.out.println("最终结果");
for (int i : value) {
System.out.print(i + ",");
}
}
public void sort(int[] value){
int insertValue = 0;
int insertIndex = 0;
for (int i = 1; i < value.length; i++) {
insertValue = value[i];
insertIndex = i -1;
//退出循环时说明找到插入的位置
while (insertIndex >= 0 && insertValue < value[insertIndex]) {
value[insertIndex + 1] = value[insertIndex];
insertIndex--;
}
if (insertIndex + 1 != i) {
value[insertIndex + 1] = insertValue;
}
System.out.println("第" + i + "趟排序");
for (int item : value) {
System.out.print(item + ",");
}
System.out.println("");
}
}
}
运行结果：
第1趟排序 1,3,4,6,2, 第2趟排序 1,3,4,6,2, 第3趟排序 1,3,4,6,2, 第4趟排序 1,2,3,4,6, 最终结果 1,2,3,4,6,
