位置p上的元素存储于tmp（第一趟p通常取1），而（位置p之前）所有更大的元素都向右移动一个位置。
然后tmp被放在正确的位置上。
代码：
public class InsertionSort {
private int q;
int[] insertionSort(int[] a) {
for (int p = 1; p < a.length; p++) {
int temp = a[p];
for (q = p; q > 0 && (temp - a[q - 1]) < 0; q--)
a[q] = a[q - 1];
a[q] = temp;
}
return a;
}
}
插入排序(InsertionSort),布布扣,bubuko.com
原文：http://www.cnblogs.com/larrylawrence/p/3787543.html