參考
Java排序算法(四)：希爾排序
常見排序算法 - 希爾排序 (Shell Sort)
數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(22)排序算法-希爾排序

希爾排序算法是按其設(shè)計者希爾（Donald Shell）的名字命名，該算法由1959年公布，是插入排序的一種更高效的改進版本。它的作法不是每次一個元素挨一個元素的比較。而是初期選用大跨步（增量較大）間隔比較，使記錄跳躍式接近它的排序位置；然后增量縮??；最后增量為 1 ，這樣記錄移動次數(shù)大大減少，提高了排序效率。希爾排序?qū)υ隽啃蛄械倪x擇沒有嚴格規(guī)定。
希爾排序是基于插入排序的以下兩點性質(zhì)而提出改進方法的：

• 插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時， 效率高， 即可以達到線性排序的效率
• 但插入排序一般來說是低效的， 因為插入排序每次只能將數(shù)據(jù)移動一位

假設(shè)有數(shù)組 array = [80, 93, 60, 12, 42, 30, 68, 85, 10]，首先取 d1 = 4，將數(shù)組分為 4 組，如下圖中相同顏色代表一組：

增量為4

然后分別對 4 個小組進行插入排序，排序后的結(jié)果為：

同顏色組內(nèi)排序

然后，取 d2 = 2，將原數(shù)組分為 2 小組，如下圖：

增量為2

然后分別對 2 個小組進行插入排序，排序后的結(jié)果為：

同顏色組內(nèi)排序

最后，取 d3 = 1，進行插入排序后得到最終結(jié)果：

增量為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 個元素的數(shù)列：[5 9 1 6 8 14 6 49 25 4 6 3]，增量d的取值依次為：6，3，1：

x 表示不需要排序的數(shù)

取 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 完全就是直接插入排序了。
越有序的數(shù)列，直接插入排序的效率越高，希爾排序通過分組使用直接插入排序，因為步長比1大，在一開始可以很快將無序的數(shù)列變得不那么無序，比較和交換的次數(shù)也減少，直到最后使用步長為1的直接插入排序，數(shù)列已經(jīng)是相對有序了，所以時間復(fù)雜度會稍好一點。

在最好情況下，也就是數(shù)列是有序時，希爾排序需要進行l(wèi)ogn次增量的直接插入排序，因為每次直接插入排序最佳時間復(fù)雜度都為：O(n)，因此希爾排序的最佳時間復(fù)雜度為：O(nlogn)。

在最壞情況下，每一次迭代都是最壞的，假設(shè)增量序列為：d8 d7 d6 ... d3 d2 1，那么每一輪直接插入排序的元素數(shù)量為：n/d8 n/d7 n/d6 .... n/d3 n/d2 n，那么時間復(fù)雜度按照直接插入的最壞復(fù)雜度來計算為：

假設(shè)增量序列為 ?N/2? ，每次增量取值為比上一次的一半小的最大整數(shù)。

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的數(shù)列和) * 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)
所以，希爾排序最壞時間復(fù)雜度為O(n^2)。

不同的分組增量序列，有不同的時間復(fù)雜度，但是沒有人能夠證明哪個序列是最好的。Hibbard增量序列：1，3，7，···，2n?1是被證明可廣泛應(yīng)用的分組序列，時間復(fù)雜度為：Θ(n^1.5)。

希爾排序的時間復(fù)雜度大約在這個范圍：O(n^1.3)~O(n2)，具體還無法用數(shù)學(xué)來嚴格證明它。

希爾排序不是穩(wěn)定的，因為每一輪分組，都使用了直接插入排序，但分組會跨越n個位置，導(dǎo)致兩個相同的數(shù)，發(fā)現(xiàn)不了對方而產(chǎn)生了順序變化。

package main

import "fmt"

// 增量序列折半的希爾排序
func ShellSort(list []int) {
    // 數(shù)組長度
    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)
}