package sort;

public class ShellSort {
   
    public static void sortByRecursive(int[] numbers, int step) {
    	// step 最小只能是1，此时表示相邻两个元素进行比较
        if (step<1){
            return;
        }

        for (int i = step; i < numbers.length; i++) {
            for (int j = i; j >= step; j -= step) {
                if (numbers[j] < numbers[j - step]) {
                    Swap.swap(numbers, j, j - step);
                }
            }
        }

        sortByRecursive(numbers,step/3);
    }

    public static int getFirstStep(int[] numbers){
        int num = numbers.length;
        int h = 1;
        while (h < num / 3) {
            h = 3 * h + 1;
        }
        return h; // h:根据数组的长度取值为 1,4,13,40.....
    }

    public static void main(String[] args) {
        int[] a = {1,3,1,4,5,6};
        int firstStep = getFirstStep(a);
        ShellSort.sortByRecursive(a,firstStep);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + "\t");
        }
    }
}

package sort;

public class Swap {
    public static void swap(int[] array, int x, int y){
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }
}