从头开始的指针i，保证其左侧都是in order的，右侧都是not yet seen的。i++，若此数比i小，则与i交换，若还比起左边的小，则再与左边的交换……
public void insertionSort(int[] a){
int N = a.length;
for(int i=0;i<N;i++){
for(int j=i;j>=0;j--){
if(a[j]<a[j-1]){
int ex = a[j];
a[j] = a[j-1];
a[j-1] = ex;
}else break;
}
}
}
insertion sort的运行时间决定于输入的order，而不像selection order那样无所谓为nn/2。insertion sort平均 大概为nn/4，最好的情况是输入恰好in order，则只需进行n-1次比较，最坏的情况是输入的是倒序的，那么就需要n*n/2次比较和交换。
其实，insertion sort的时间复杂度和输入array中invertion的元素数量是呈线性关系的。
