思路
low为改数组中还没有排序的索引位置，t代表该索引位置的值
我们只需要将low与前面排好序的数组比较，找到第一个比t小的值，将t排在它后面即可
未排序部分不断缩小，直到i缩小到0或者low的前一位值已经比low的值小，此时退出查找
我们来看代码
public class InaertionSort {public void sort(int[] a) {Insertion(a,1);}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);}
}
问题一：
这种情况，其实low就算向前查找也不需要交换，而在完成a[i+1]=t的时候其实是重复赋值了
我们可以这样改进代码
//找到插入位置if(i+1!=low){a[i+1]=t;}问题二：
在代码中，我们完成了交换操作，我们来比较一下两种代码：
这个是我们写的
这个是另外一种：
两种方法都能完成交换操作，但是第一种的效率更好，操作更省。
