希尔排序

希尔排序是属于插入排序的一种，即分组进行插入排序，将大数和小数适当的分布于左右，减少插入时移动的次数

package string.sort.insert;

import java.util.Arrays;

/**
 * @author chenyi
 * @Description
 * @date 2022/2/14 11:36
 */
public class ShellSort {

    public void solution(int[] arr) {
        // 步长，初始为数据长度的一半
        for (int gap = arr.length>>1; gap > 0; gap>>=1) {
            for (int i = gap; i < arr.length; i++) {
                int temp = arr[i];
                // 分组进行插入排序，每组第一个不动.用排好序的最近一个数和当前数比较
                int j = i;
                while (j-gap>=0 && arr[j-gap]>temp) {
                    arr[j] = arr[j-gap];
                    j-=gap;
                }
                arr[j] = temp;
            }
            System.out.println(Arrays.toString(arr));
        }
    }

    public static void main(String[] args) throws InterruptedException {
        int[] arr = {8,9,1,7,2,3,5,4,6,0};
        new ShellSort().solution(arr);
    }

}