Shell排序

一、思路

###二、结论

1. 当gap = n 时，就得比较 array.length - n 次
2. shell排序用移位法比取出来交换然后在插入效率高很多

三、代码

public class ShellSort {
    public static void main(String[] args) {
//        int[] array = new int[]{1, 9, 4, 6, 7, 2, 8, 3, 5};
        int[] array = new int[]{1, 4, 6, 2, 3, 5, 8};
        int[] sort = shellSort(array);
        System.out.println(Arrays.toString(sort));
    }
    public static int[] shellSort(int[] array) {
        for (int i = array.length / 2; i > 0; i = i / 2) {
            for (int j = i; j < array.length; j++) {
                int index = j - i;
                int indexVal = array[j];
                while (index >= 0 && indexVal < array[index]) {
                    array[index + i] = array[index];
                    index -= i;
                }
                array[index + i] = indexVal;
            }
        }
        return array;
    }
}