我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

示意图

参考文章：十大经典排序算法

1.3 代码演示

package com.zhuang.algorithm;

import java.util.Arrays;

/**
 * @Classname ShellSort
 * @Description 希尔排序
 * @Date 2021/6/13 18:23
 * @Created by dell
 */

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {51, 46, 20, 18, 65, 97, 82, 30, 77, 50};
        shellsort(arr);
        System.out.println("希尔排序以后的序列为:");
        System.out.println(Arrays.toString(arr));//[18, 20, 30, 46, 50, 51, 65, 77, 82, 97]
    }

    public static void shellsort(int[] array) {
        int len = array.length;
        int temp, gap = len / 2;
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                temp = array[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && array[preIndex] > temp) {
                    array[preIndex + gap] = array[preIndex];
                    preIndex -= gap;
                }
                array[preIndex + gap] = temp;
            }
            gap /= 2;
        }
    }
}