Java常用排序算法-希尔排序（Shell Sort）

希尔排序是一种改进的插入排序算法，它的基本思想是将待排序的数组按照一定的间隔进行分组，对每组使用插入排序算法进行排序，然后缩小间隔，再对分组进行排序，直到间隔为1为止。
逐渐减小间隔大小的方法有助于提高排序过程的效率，可以减少比较和交换的次数。这是希尔排序算法的一个关键特点。

//希尔排序
public void test4() {
	//第一轮比如步长为5,拿出array[i],array[i+5]...,6与5,2与7,8与9等排序后array = {6, 2, 8, 3, 1, 5,7,9,4};
	//第二轮比如步长为3,第二轮拿出array[i],array[i+3]...,6与3与7,2与1与9,8与5与4,排序后array = {3, 1, 4, 6, 2, 5,7,9,8};
	//第三轮比如步长为1,进行插入排序
    int[] array = {5, 2, 8, 3, 1, 6,7,9,4};
    int increment = array.length / 2;
    while (increment >= 1){
        for (int i = increment; i < array.length; i++) {
            int j = i - increment;
            int temp = array[i];
            // 寻找插入位置并移动数据
            while (j >= 0 && array[j] > temp) {
                array[j + increment] = array[j];
                j -= increment;
            }
            array[j + increment] = temp;
        }
        // 设置新的增量
        increment /= 2;
    }
    //arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    System.out.println("arr = " + Arrays.toString(array));
}