一、思想-什么是插入排序
插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。和打扑克牌时整理牌类似，假设你拿到的牌中有一个顺子，但是刚拿到的牌是乱序的，你需要将它整理好，也就是进行一个排序，你可以这样整理：从一张牌开始，拿它后面的牌和它进行比较，若后面的牌小于前面的牌，则将后面这张牌拿出来插入到它前面这张牌的前面，这样就是插入排序，不断地重复这个过程就可以将你的顺子整理好了。
二、例子
一个数组，我们可以分成已排序部分和非排序部分，现在我们要将非排序部分中的一个元素插入到已排序部分中。
现在我们将数组中的第一个元素（索引=0）设置为已排序部分的上边界，让一个指针i指向它。此元素后面的部分属于未排序区域，给一个指针low指向这个未排序区域的下边界（索引=1）。这两个指针的关系是i = low - 1,它们是相邻的。
排序的时候我们就选取low指针指向的元素与i指针指向的元素进行比较。先将low指针指向的元素放到一个临时变量t里面（因为等会进行比较的时候low指向的索引位置可能会被覆盖掉，这是为了给要插入的元素腾出一个位置，相当于我们把牌拿出去之后再放进来。）。
若low指向的元素大于i指向的元素，则a[i+1] = t,然后继续递归，继续调用函数insertion(a,low + 1)，注意此时low已经变成了low+1,也就是说未排序部分的下边界已经右移了一位；
若low指向的元素小于i指向的元素，则a[i + 1] = a[i]，将索引为i的元素的值赋值给索引为i+1的元素，注意这个时候a[i+1]就被覆盖掉了，而我们前面说过i = low - 1，那么low = i + 1,也就是这个low指向的元素被覆盖了，所以我们前面要设置一个临时变量来保存a[low]的值，接下来i--,即指针i左移，继续来寻找比t小的值。
当i<0时退出循环，执行下面的a[i + 1] = t，这时i = -1，所以有a[0] = t,意思就是将这个t放在了第一位。
随着我们的递归不断地进行，已排序的区域就会不断地增大，未排序的区域就会不断地缩小，直到最后我们将元素全部都排好序。
结束递归的条件就是未排序部分的下边界等于数组长度。
三、Java代码实现
1.递归部分-我们先写出递归的框架
/*写一个递归函数insertion 它接受两个参数
* 1.int[] a整个需要进行排序的数组
* 2.int low未排序区域的下边界 */
private static void insertion(int[] a,int low){
/*low等于数组长度时，我们就停止递归，这里是递归出口*/
if(low == a.length){
return;
}
/*当low小于数组长度时，继续进行递归，未排序区域的边界向右移*/
insertion(a,low + 1);
}2.排序部分-排序的实现
/*先将low指针指向的变量的值存储到一个临时变量里面，
目的是之后我们要用它与已排序区域中元素的值进行比较,
因为a[i + 1] = a[i];之后low这个位置就会被覆盖掉。
比较之后我们才能确定这个元素的插入位置*/
int t = a[low];
int i = low - 1;/*变量i代表已排序区域的一个指针，low - 1就是已排序区域的上边界*/
/*从已排序部分的右边相左找，就能找到第一个比t小的元素，然后就能将t插入了*/
while(i >= 0 && a[i] > t){//没有找到要插入的位置时，不断进行循环，直到找到为止
a[i + 1] = a[i];//空出插入位置
i--;//指针i 左移
}
a[i + 1] = t;//a[i] < t 时退出循环，找到了插入位置3.完整代码
/*我们可以对外暴露一个更容易使用的函数sort
* 这里的sort函数只接收一个参数int[] a
* 在sort里面我们再来调用insertion函数，未排序下边界我们设置为1.*/
public static void sort(int[] a){
insertion(a,1);
}
/*insertion函数，用来进行递归插入排序*/
private static void insertion(int[] a,int low){
if(low == a.length){
return;
}
int t = a[low];
int i = low - 1;
while(i >= 0 && a[i] > t){
a[i + 1] = a[i];
i--;
}
a[i + 1] = t;
insertion(a,low + 1);
}
}