public class ShellSort {

    // 先将整个待排序的记录序列分割成为若干子序列，分别进行直接插入排序；
    // 待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
    public static void shellSort(int[] a) {
        int h = 1;
        while (h < a.length/3)
            h = 3*h + 1;

        while (h >= 1) {
            // 将数组变为h有序
            for (int i = h; i < a.length; i++) {
                // 将a[i]插入到a[i-h]、a[i-2*h]、a[i-3*h]...之中
                for (int j = i; j >= h && a[j] < a[j-h]; j -= h) {
                    int temp = a[j];
                    a[j] = a[j-h];
                    a[j-h] = temp;
                }
            }
            h = h/3;
        }
    }

    public static void main(String[] args) {
        int[] a = new int[] {2, 4, 7, 5, 11, 3, 1, 9, 7, 8, 10, 6, 2, -1, 0};
        shellSort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

}