【三、希尔排序】

希尔排序： 先追求表中元素部分有序，再逐渐逼近全局有序
1.先将待排序表分割为若干形如 L[i,i+d,i+2d,…,i+kd]的"特殊"子表，即把相隔某个 "增量 " 的记录组成一个子表
2.对各个子表分别进行直接插入排序
3.当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。

public class 希尔排序 {
    public static void main(String[] args) {
//        int nums[]={6,1,3,2,4};
        int nums[]={49,38,65,97,76,13,27,49,55,04};
        sort(nums);
        System.out.println(Arrays.toString(nums));
    }
    static void sort(int[]nums){
        int n = nums.length;
        int j,dk;
        for (dk=n/2;dk>=1;dk=dk/2){   //步长变化
            //注意此处
            for (int i=dk;i= 0
                    //给 "同一个子表" 中 "后面的小元素" 的插入位置腾出空间
                    for (j=i-dk;j>=0 && temp