参考
Java排序算法(四)：希尔排序
常见排序算法 - 希尔排序 (Shell Sort)
数据结构和算法(Golang实现)(22)排序算法-希尔排序

希尔排序算法是按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布，是插入排序的一种更高效的改进版本。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步（增量较大）间隔比较，使记录跳跃式接近它的排序位置；然后增量缩小；最后增量为 1 ，这样记录移动次数大大减少，提高了排序效率。希尔排序对增量序列的选择没有严格规定。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率
• 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位

假设有数组 array = [80, 93, 60, 12, 42, 30, 68, 85, 10]，首先取 d1 = 4，将数组分为 4 组，如下图中相同颜色代表一组：

增量为4

然后分别对 4 个小组进行插入排序，排序后的结果为：

同颜色组内排序

然后，取 d2 = 2，将原数组分为 2 小组，如下图：

增量为2

然后分别对 2 个小组进行插入排序，排序后的结果为：

同颜色组内排序

最后，取 d3 = 1，进行插入排序后得到最终结果：

增量为1

该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

public class ShellSort {

    public static void main(String[] args) {
        int[] arr = { 6, 5, 3, 1, 8, 7, 2, 4 };
        System.out.println("排序之前：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

        // 希尔排序
        shellSort(arr);

        System.out.println();
        System.out.println("排序之后：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    /**
     * 希尔排序
     */
    private static void shellSort(int[] arr) {
        int j;
        for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
            for (int i = gap; i < arr.length; i++) {
                int tmp = arr[i];
                for (j = i; j >= gap && tmp < arr[j - gap]; j = j - gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = tmp;
            }
        }
    }

}

举个简单例子，希尔排序一个 12 个元素的数列：[5 9 1 6 8 14 6 49 25 4 6 3]，增量d的取值依次为：6，3，1：

x 表示不需要排序的数

取 d = 6 对 [5 x x x x x 6 x x x x x] 进行直接插入排序，没有变化。
取 d = 3 对 [5 x x 6 x x 6 x x 4 x x] 进行直接插入排序，排完序后：[4 x x 5 x x 6 x x 6 x x]。
取 d = 1 对 [4 9 1 5 8 14 6 49 25 6 6 3] 进行直接插入排序，因为 d=1 完全就是直接插入排序了。
越有序的数列，直接插入排序的效率越高，希尔排序通过分组使用直接插入排序，因为步长比1大，在一开始可以很快将无序的数列变得不那么无序，比较和交换的次数也减少，直到最后使用步长为1的直接插入排序，数列已经是相对有序了，所以时间复杂度会稍好一点。

在最好情况下，也就是数列是有序时，希尔排序需要进行logn次增量的直接插入排序，因为每次直接插入排序最佳时间复杂度都为：O(n)，因此希尔排序的最佳时间复杂度为：O(nlogn)。

在最坏情况下，每一次迭代都是最坏的，假设增量序列为：d8 d7 d6 ... d3 d2 1，那么每一轮直接插入排序的元素数量为：n/d8 n/d7 n/d6 .... n/d3 n/d2 n，那么时间复杂度按照直接插入的最坏复杂度来计算为：

假设增量序列为 ⌊N/2⌋ ，每次增量取值为比上一次的一半小的最大整数。

O( (n/d8)^2 + (n/d7)^2 + (n/d6)^2 + ... + (n/d2)^2 + n^2)

= O(1/d8^2 + 1/d7^2 + 1/d6^2 + ... + 1/d2^2 + 1) * O(n^2)
= O(等比为1/2的数列和) * O(n^2)
= O(等比求和公式) * O(n^2)
= O( (1-(1/2)^n)/(1-1/2) ) * O(n^2)
= O( (1-(1/2)^n)2 ) * O(n^2)
= O( 2-2(1/2)^n ) * O(n^2)
= O( < 2 ) * O(n^2)
所以，希尔排序最坏时间复杂度为O(n^2)。

不同的分组增量序列，有不同的时间复杂度，但是没有人能够证明哪个序列是最好的。Hibbard增量序列：1，3，7，···，2n−1是被证明可广泛应用的分组序列，时间复杂度为：Θ(n^1.5)。

希尔排序的时间复杂度大约在这个范围：O(n^1.3)~O(n2)，具体还无法用数学来严格证明它。

希尔排序不是稳定的，因为每一轮分组，都使用了直接插入排序，但分组会跨越n个位置，导致两个相同的数，发现不了对方而产生了顺序变化。

package main

import "fmt"

// 增量序列折半的希尔排序
func ShellSort(list []int) {
    // 数组长度
    n := len(list)

    // 每次减半，直到步长为 1
    for step := n / 2; step >= 1; step /= 2 {
        // 开始插入排序，每一轮的步长为 step
        for i := step; i < n; i += step {
            for j := i - step; j >= 0; j -= step {
                // 满足插入那么交换元素
                if list[j+step] < list[j] {
                    list[j], list[j+step] = list[j+step], list[j]
                    continue
                }
                break
            }
        }
    }
}

func main() {
    list := []int{5}
    ShellSort(list)
    fmt.Println(list)

    list1 := []int{5, 9}
    ShellSort(list1)
    fmt.Println(list1)

    list2 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
    ShellSort(list2)
    fmt.Println(list2)

    list3 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3, 2, 4, 23, 467, 85, 23, 567, 335, 677, 33, 56, 2, 5, 33, 6, 8, 3}
    ShellSort(list3)
    fmt.Println(list3)
}