希尔排序

public static void main(String[] args) {
        int a[]={12,3,55,58,47,83,21,7,39,75};
        sort(a);
    }
    public static void sort(int[] a){
//        /增量gap，并逐步缩小增量
        for (int gap = a.length/2; gap >0 ; gap/=2) {
//            while (gap < len / 3) {          // 动态定义间隔序列
//                gap = gap * 3 + 1;
//            }
//            //从第gap个元素，逐个对其所在组进行直接插入排序操作
            for (int i = gap; i <a.length ; i++) {
                int j=i;
                int t=a[i];
//                 //移动法
                    while(j-gap>=0&&t<a[j-gap]){
                        a[j]=a[j-gap];
                        j-=gap;
                    }
                    a[j]=t;
            }
        }
        System.out.println(Arrays.toString(a));
    }      

原理：

缩小增量

希尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。

排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。