insertion sort

从头开始的指针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的元素数量是呈线性关系的。