直接插入排序
概念
直接插入排序就是将一堆数据分为两个部分(思想上分开而已，实际上还是在同一个数组中)，一部分是有序的，一部分是无序的，每次从无序表中找一个需要插入有序表中值，找到有序表中合适的位置插入，这个合适的位置就是说这个新的值插入之后有序表仍然是有序的。n个数据，一开始第一个放在有序表，剩下n-1个放在无序表，等到无序表中每一个都找出来插入到无序表中的时候就排序完毕了。
(直接)插入排序.gif
看这个动态图，你会很直观清晰的理解直接插入排序，注意每次比对有序表中的一个值的时候，如果有序表中那个值比现在要插入的值大的话需要往后面移动的，所以插入的值需要用一个变量保存起来，这样就可以将原来无序表的位置直接覆盖了。
思路分析
- 一开始无序表有n-1个数据，所以需要一个一个拿出来插入有序表中，需要n-1趟
- 每一趟取出无序表第一个，也就是有序表最后一个下标位置加一那个值，保存这个insertVal和insValIndex，和无序表中从后往前进行比较，比当前比较的有序表的数小则那个有序表的数后移。
代码实现
感觉挺简单的东西越说越复杂了一样，看看代码应该很容易就理解了。
package _6_sort;
import java.util.Arrays;
import java.util.Date;
/**
* author waigo
* create 2021-01-27 9:54
*/
public class InsertSort {
public static void insertSort(int[] data) {
for (int i = 1; i < data.length; i++) {//n-1次,一开始有序表就一个数，下标为0
int insertVal = data[i], insValIndex = i - 1;//插入值就是当前无序表的第一个，尝试插入无序表最后一个位置
//insValIndex = i - 1比起insValIndex = i来说好处是每一种情况下都是一样的，最后都是插入insValIndex+1的位置，不用进行多一个判断
while (insValIndex >= 0 && insertVal < data[insValIndex]) {
data[insValIndex + 1] = data[insValIndex];//插入位置那个数后移
insValIndex--;//插入位置往前移
}
//当前insValIndex找到的就是比insertVal小的那个数，插入到insValIndex+1的位置
data[insValIndex + 1] = insertVal;
}
}
public static void main(String[] args) {
int[] arr = RandomProducer.produceRandom(5,10000,80000);
// int[] arr = {101,34,119,1};
// System.out.println("排序前");
// System.out.println(Arrays.toString(arr));
Date from = new Date();
insertSort(arr);
// System.out.println("排序后");
// System.out.println(Arrays.toString(arr));
System.out.println("运行了"+(new Date().getTime() - from.getTime())+"毫秒");
//测试80000个随机数的排序，大概0.8秒，比冒泡18s和简单选择4s快多了
}
}
