直接插入排序

对于一个有n个元素的待排序列，将这个序列分成有序表和无序表，刚开始时，有序表只有一个元素，无序表有n-1个元素，排序过程就是将无序表的第一个元素插入到有序表的合适位置，依次循环n-1次。

public static void insertsort(int[] arr) {
    int i, j, k;
    for(i=1;i<arr.length;i++) {
        for(j=i-1;j>=0;j--) {
            if(arr[j]<arr[i])
                break;
        }   
        if(j!=i-1) {
            int temp = arr[i];
            for(k = i-1;k>j;k--) {
                arr[k+1] = arr[k];
            }
            arr[j+1]=temp;
        }
    }
}
public static void main(String[] args) {
    int[] arr = {62,23,51,46,85,42,15};
    insertsort(arr);
    System.out.println(Arrays.toString(arr));
}

最好情况：待排序列已按关键字有序，只需1次比较，0次移动。
总比较次数：n-1次
总移动次数：0次
最坏情况：待排序列按关键字逆序，即每趟都需要叫关键字插入到有序序列的第一位
总比较次数：（n+2）（n+1）/2
总移动次数：（n+4）（n-1）/2

平均情况：O(n2)