插入排序

    /**
     * 插入排序
     *
     * 从第一个元素开始，该元素可以认为已经被排序
     * 取出下一个元素，在已经排序的元素序列中从后向前扫描
     * 如果该元素（已排序）大于新元素，将该元素移到下一位置
     * 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
     * 将新元素插入到该位置中
     * 重复步骤2
     * @param array  待排序数组
     */
    public static void insertSort(int[] array) {
        int length = array.length;
        int i, j, temp;
        // 正序遍历的未排序的部分（第一个元素认为是已排好序的）
        for (i=1;i<length;i++) {
            // temp记录需要插入的元素
            temp = array[i];
            // 倒序遍历已排序部分
            // 找到比temp大的元素向后移动
            for(j=i-1;j>=0&&temp<array[j];j--) {
                array[j+1] = array[j];
                // 移动完后j--，则此时j位于需要插入的位置的前一位
            }
            // temp插入到的位置前面比temp小，后面比temp大
            array[j+1] = temp;
        }
    }