按步长i(初始值=length/2)分组,组内直接插入排序
    步长i=i/2,继续分组排序,直到i=1
    时间复杂度 nlog(n)
    附上JAVA代码
    /**
    * 希尔排序 shell
    步长i(length/2)分组,组内直接插入排序
    步长i=i/2,继续分组排序,直到i=1
    * @param a
    */
    public void shell(Integer[] a){
    System.out.println(“开始前,a:” + Arrays.toString(a));
    for (int i = a.length/2; i > 0 ; i/=2) {//i是步长,初始值按总个数/2,每次/2
    for (int j = 0; j < i; j++) {//循环1个步长
    insert3(a,j,i);//带步长的插入排序
    }
    }
    System.out.println(“开始后,a:” + Arrays.toString(a));
    }

    /**
    * 带步长的插入排序
    * @param a 数组
    * @param start 开始下标
    * @param delta 步长
    */
    public void insert3(Integer[] a,int start,int delta){
    int value;//存储要比对的值
    for (int i = start + delta; i < a.length; i += delta) {//从第2个元素开始,直到结束
    value = a[i];//将要比对的值赋值给value
    int j;
    for (j = i; j-delta >= 0; j-=delta) {//j是要排序的数,先和左边排序好的最右边的数据(j-delta)比较大小,每次左移delta位
    //System.out.println(“i:” + i +”,j:” + j + “,a[i]:” + a[i] + “,a[j-delta]:” + a[j-delta]);
    if (value < a[j - delta]) {//如果左边的值比较大
    a[j] = a[j - delta];//左边的值右移delta位
    } else {
    break;
    }
    }
    a[j] = value;//最后将比对的值赋值给结束为止
    }
    }