本文共 1149 字，大约阅读时间需要 3 分钟。

希尔排序

是插入排序的升级版，设置一个gap增量把未排序序列分组、插入排序，继续缩小gap分组、插入排序直至gap为1。只需最后微调一下，就OK啦。

算法步骤：

1.设定gap将序列分组

直接上代码

private int[] shellSort(int[] source) {
           // 对 arr 进行拷贝，不改变参数内容        //8 9 1 7 2 3 5 4 6 0        int[] arr = Arrays.copyOf(source, source.length);        int gap = 1;        while (gap < arr.length) {
               gap = gap * 3 + 1;        }                while (gap>0){
               //通过这种方式，首次分组为[8,2]、[9,3]...            for (int i = gap; i < arr.length; i++) {
                   int tmp = arr[i];                int j = i - gap;                //这个while是为了把分组内的元素，通过插入排序来排列                //比如第一轮第一组，[8,2]，while里面把8赋值给了index=4                while (j >= 0 && arr[j] > tmp){
                       arr[j + gap] = arr[j];                    j-=gap;                }                //上面while结束后，把第一轮第一组的[8,2]中的2赋值给了index=0的位置，                //实现了第一轮第一个分组的排序，[8,2]变成了[2,8]                arr[j + gap] = tmp;                //第一轮第一组处理完后，开始处理第一轮第二组[9,3]            }            //for循环结束了，代表第一轮排序完成，缩小gap，继续...            gap = (int) Math.floor(gap / 3);        }        return arr;    }