将右侧待排序的数据,逐个插到左边已排序的数据中的正确位置
    初步认定第1个是已经排序好的,从第2个开始
    先和左边排序好的最右边的数据比较大小
    时间复杂度 n
    附上JAVA代码
    public void insert2(Integer[] a){
    System._out    .println(“开始前,a:” + Arrays.toString(a));
    int value;//存储要比对的值
    for (int i = 1; i < a.length; i++) {//从第2个开始,知道结束
    value = a[i];//将要比对的值赋值给value
    int j;
    for (j = i; j > 0 ; j—) {//j是要排序的数,先和左边排序好的最右边的数据(j-1)比较大小,每次左移1位
    //System.out.println(“i:” + i +”,j:” + j + “,a[j]:” + a[j] + “,a[j-1]:” + a[j-1]);
    if(value < a[j-1]){//如果左边的值比较大
    a[j] = a[j-1];//左边的值右移1位
    }else{
    break;
    }
    }
    a[j] = value;//最后将比对的值赋值给结束为止
    //System.out.println(“执行” + String.valueOf(i+1) + “次,a:” + Arrays.toString(a));
    }
    System.out.println(“开始后,a:” + Arrays.toString(a));
    }