public class b希尔排序 {
    //希尔排序也称缩小增量排序
    public static void F(int[] arr){
        //过程：将arr[i]给temp,j=i-1,while条件满足，将arr[j]给arr[j+1],直到不满足while条件，将arr[i]与当前的arr[j+1]互换
        for(int index=arr.length/2;index>0;index=index/2){   //分组
            for(int i=index;i<arr.length;i++){
                int temp=arr[i];
                int j=i-index;
                while(j>-1&&temp<arr[j]){
                    arr[j+index]=arr[j];
                    j=j-index;
                }
                arr[j+index]=temp;
            }
        }
    }

    public static void F1(int[] arr){    //插入排序
        for(int i=1;i<arr.length;i++){
            int temp=arr[i];                //   i=1时     i=2时
            int j=i-1;                      //   9,8       8,9,7
            while(j>-1&&temp<arr[j]){       //   9,9       8,9,9
                arr[j+1]=arr[j];            //   8,9       8,8,9
                j--;                        //             7,8,9
            }
            arr[j+1]=temp;
        }
    }
    public static void main(String[] args) {
        int[] arr={9,8,7,6,5,4,3,2,1};
        F(arr);
        System.err.println(Arrays.toString(arr));
    }
}