插入排序基本原理

将待排序列表看成有序和无序的两部分，初始为有长度为1的有序数组和其后的无序数组。之后从无序数组中取出第一个数a与有序数组从后往前进行比较，如果a小于被比较的数则与之交换，否则说明a已经到了有序数组中合适的位置。此时，有序数组长度+1，无序数组长度-1，如此操作直到全部有序。

代码实现

    public static <T extends Comparable> void insertSort(T[] a ){
        for(int i = 1; i < a.length; i++){
            for(int j = i; j > 0; j--){
                if(a[j-1].compareTo(a[j])>0){
                    T t = a[j];
                    a[j] = a[j-1];
                    a[j-1] = t;
                }
                else
                    break;
            }
        }
    }