高级排序 --- 希尔排序（常见经典排序算法）

import java.util.Arrays;
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {3, 45, 78, 99, 45, 64, 55, 52, 11, 18, 66, 17, 37, 199, 120, 54, 49};
        System.out.println("未排序数组："+ Arrays.toString(arr));
       shellSort(arr);
        System.out.println("已排序数组："+Arrays.toString(arr));
    }
    //希尔排序和插入排序相似，多了一个循环进行分组排序
    public static void shellSort(int[] arr){
        //步长  gap
        for (int gap=arr.length/2;gap>0;gap /=2){//步长可以自定义，可以除2也可以除3...（下面步骤和插入排序步骤一样）
            for (int i=gap;i<arr.length;i+=gap){//每次增加一个步长的长度
                int insertIndex = i;
                int insertValue = arr[i];
                while (insertIndex-gap >= 0 && insertValue < arr[insertIndex - gap]){
                    arr[insertIndex] = arr[insertIndex - gap];
                    insertIndex -= gap;
                }
                arr[insertIndex] = insertValue;
            }
        }
    }
}