直接插入排序是一种最简单的排序算法，在后续我会继续发布其他的简单排序；直接插入的算法基本思想是：仅有一个元素的序列总是有序的，因此，对n个记录的序列，可从第二个元素开始直接到第n个元素，逐个向有序序列中执行插入操作，从而得到n个元素按关键字有序的序列。一般来说，在含有j-1个元素的有序序列中插入一个元素的方法是：从第j-1个元素开始依次向前搜索应当插入的位置，并且在搜索插入位置的同时可以后移元素，这样当找到适当的位置时，即可插入元素。
或许上面的讲解比较官方一点，说的通俗一点，给你一个无序的数组，或者一段需要排序的序列，我们通常用第一个元素作为参考值，从第二个元素开始和这个参考值进行比较，比这个参考值大的时候放在这个参考值的后面，比这个参考值小的时候在和这个参考值的前一位进行比较，当比较至适当位置进行插入。下面是我偷来的一张图：
偷来的图.png
下面是书上给的一个直接插入的算法例子：
输入：数组元素数组r，数组r的待排序区间[low,high]
输出：数组r以关键字有序
public void insertSort(Object[] r,int low,int high){
for(int i = low +1;i<=high;i++){ //小于时，需要将r[i]插入有序列表
if(r[i] < r[i-1]){
Object temp = r[i];
r[i] = r[i-1];
int j=i-2;
for(;j>=low&&temp < r[j];j++){
r[j+1] = r[j];//记录后移
}
r[j+1] = temp;//插入到正确位置
}
}
}
这是书上的算法，但是个人感觉看起来比较生涩，所以自己写了一个例子，进行对比，
public class ZhijieCharuPaixu {
public static void main(String[] s) {
int[] a = {1,2,3,0};
insertSort(a,0,a.length);
for(int n : a){
System.out.print(n+" ");
}
}
/**直接插入排序**/
public static void insertSort(int[] object,int low,int high) {
//将第一个值看做一个有序序列
for(int i = 1;i<high;i++) {
if(object[i] < object[i-1]) {
int temp = object[i];//待比较的数值
int j = i-1;
for(;j >=low&&object[j] > temp;j--) {
object[j+1] = object[j];
}
//比较完成后获得j最后的位置
object[j+1] = temp;
}
}
}
}
和书上的进行对比，感觉，i-1位置的数值不用赋值给i位置
现在对我写的这个例子进行分析：
前三个位置的数字是从小到大一次进行排序的，在if（object[i] < object[i-1]条件下不会进行排序，直接对最后位置的0和前面的数值进行比较，直观来看，排序之后应该是0,1,2,3这样一个顺序。进入循环后第一次循环：
1.png
2.png
3.png
QQ图片20190105164707.png
这是通过断点，进行的分析，最后一次的插入的位置正是第一个位置（可以自己换成其他的数据进行检验）
空间效率：仅使用一个辅助单元
时间效率：假设待排序的元素个数为n,则向有序表中逐个插入记录的操作进行了n-1趟，每趟操作分为比较关键代码和移动记录，而比较的次数和移动的次数取决于待排序列关键代码的初始排列
- 最好的情况下，即待排序序列按关键字已经有序排列，每趟操作只需1次或者0次移动
- 在最坏的情况下，即待排序序列按关键字逆排序序列，这时在第j趟操作中，为插入元素需要同前面的j个元素进行j次关键字比较，移动元素的次数为j+1次。此时有：总比较次数=n(n-1)/2次，总移动次数 = （n+2)(n-1)/2次
- 平均情况下：即在第j趟操作中，插入记录大约需要时间同前面的j/2个元素进行关键字比较，移动记录次数j/2+1次
- 直接插入排序的时间复杂度：O（n2）
