视频https://www.bilibili.com/video/BV1E8411e718

package com.horse;

import java.util.Arrays;

public class Sort {
    public static void main(String[] args) {
        int arr[] = {4, 1, 8, 2, 3, 11, 12, 0, 10, 6};
        System.out.println(Arrays.toString(arr));//打印排序前数组
        sort(arr);
        System.out.println(Arrays.toString(arr));//打印排序后数组
    }

    public static void sort(int[] a) {
        //希尔排序
        int gap = a.length;
        while (true) {
            gap /= 2;   //增量每次减半
            for (int i = 0; i < gap; i++) {
                for (int j = i + gap; j < a.length; j += gap) {//这个循环里其实就是一个插入排序
                    int k = j - gap;
                    while (k >= 0 && a[k] < a[k + gap]) {//这里的插入算法是换位类型的
                        int temp = a[k];
                        a[k] = a[k + gap];
                        a[k + gap] = temp;
                        k -= gap;
                    }
                }
            }
            if (gap == 1)
                break;
        }
    }
}