排序－插入

插入排序算法比冒泡 和选择 略微复杂些，但效率好些。

插入排序总是假设指定位置的左边的数组是有序的，而后将指定位置的值插入左边的有序数组。

指定的位置从下标1开始，每次循环递增1，直到数组结束。

插入排序的比较次数与交换次数的时间效率均为O(n^2)，确切的说是O(n^2 / 4)，比冒泡排序快一倍。

对于一个基本有序数组，由于内循环基本都是空循环，插入排序的效率接近O(n)，但对于完全逆序数组，插入排序的效率与冒泡相同。因此插入排序对于 基本有序，或反复排序的数组比较有利，实是上插入排序常常用于其他排序的首尾工作，其他排序只要排到基本有序即可，比如快速排序。

下面是代码。

class Insert {
    public static void main(String[] args) {
        int[] a = {1,5,3,8,4,3,8};
        sort(a);
        print(a);
    }

    private static void sort(int[] a) {
        int temp;
        for(int i=1; i<a.length; i++) {
            int pos = i;        //确定位置，在此位置左边的数组是有序的。
            temp = a[i];         //根据位置确定要插入的数值。
            while(pos>0 && a[pos-1]>temp) {   //选择第一个不大于要插入数值的的位置
                a[pos] = a[pos - 1];   //将数据以此向后移动
                pos--;
            }
            a[pos] = temp;   //将指定数值插入恰当位置
        }
    }

    private static void print(int[] a) {
        for(int i: a) System.out.print(i + " ");
        System.out.println();
    }
}