算法描述:

① 定义一个增量序列Dm > Dm-1 > ...>D1 = 1；

② 对序列进行m趟排序，对每个Dk进行 “Dk-间隔” 排序；

package com.lin;

public class ShellSort {
    public static void main(String[] args) {

        System.out.println("=====希尔排序=====");
        int[] array = new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        System.out.println("排序之前：");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }

        //直接插入排序
        array = shellSort1(array);

        System.out.println("\n");
        System.out.println("排序之后：");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }

    /*
     * 原始的希尔排序:
     * 最大间隔为数组长度的一半
     * 剩余的间隔增量为原来的一半，gap / 2
     */
    public static int[] shellSort(int[] arr) {
        int gap = arr.length / 2;
        while(gap > 0){
            for (int i = gap; i < arr.length; i++) {
                int temp = arr[i];
                int j = i - gap;
                while(j >= 0 && arr[j] > temp){
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = temp;
            }
            gap /= 2;
        }
        return arr;
    }

    /*
     *  优化的希尔排序:
     *  增量初始值为1，通过3 * gap + 1循环计算，一直得到gap刚好不大于数组长度的三分之一。
     *  此时就取gap做最大间隔，然后通过gap / 3 计算剩下的增量
     *  while(gap < arr.length / 3){
     *      gap = gap * 3 + 1;
     *  }
     *
     * */
    public static int[] shellSort1(int[] arr) {
        int gap = 1;
        while(gap < arr.length / 3){
            gap = gap * 3 + 1;
        }
        while(gap > 0){
            for (int i = gap; i < arr.length; i++) {
                int temp = arr[i];
                int j = i - gap;
                while(j >= 0 && arr[j] > temp){
                    arr[j + gap] = arr[j];
                    j -= gap;
                }
                arr[j + gap] = temp;
            }
            gap /= 3;
        }
        return arr;
    }
}