希尔排序（Shell Sort）

public static void main(String[] args) {
    int[] arr = {9, 6, 8, 4, 2, 5, 7, 3, 1};
    int[] arr2 = {9, 6, 8, 4, 2, 5, 7, 3, 1};
    shellSort(arr);
    System.out.println("=====================");
    shellSort2(arr2);
}

/**
 * shell排序，插入排序的优化
 * 最终也是使用插入排序，区别就是找到间隔数，可以理解插入排序就是间隔为1的shell排序
 * 其实可以这样理解，把gap换成1，代入就行了，只有gap是需要变换的，其他代码就是插入排序的代码
 * 复杂度O(n^1.3)
 * @param arr
 */
private static void shellSort(int[] arr) {
    for (int gap = arr.length / 2; gap > 0; gap /= 2){
        for (int i = gap; i < arr.length; i++) {
            int min = arr[i];
            int j = i - gap;
            while (j >= 0 && min < arr[j]) {
                arr[j + gap] = arr[j];
                j -= gap;     //每次j就是减去gap个间隔数，其实gap是1的话就是j--
            }
            if (arr[j + gap] != min) {    //如果相等,可不用替换,这样就可以减少替换的次数
                arr[j + gap] = min;
                System.out.println(Arrays.toString(arr));
            }
        }
    }
}


/**
 * shell排序,for循环的形式
 * @param arr
 */
private static void shellSort2(int[] arr) {
    //表示每次的间隔是原来的一半，这样最终的间隔一定会有1的间隔
    int temp = 0;
    for (int gap = arr.length / 2; gap > 0 ; gap /= 2) {
        for (int i = gap; i < arr.length; i++) {
            for (int j = i; j > gap - 1 ; j -= gap) {
                if (arr[j] < arr[j - gap]) {
                    temp = arr[j];
                    arr[j] = arr[j - gap];
                    arr[j - gap] = temp;
                    System.out.println(Arrays.toString(arr));
                }
            }
        }
    }
}