[golang] 數據結構-希爾排序

除了上篇介紹的二分插入排序，還有這次介紹的希爾排序(Shell's Sort)，也是對直接插入排序算法的優化。

原理
希爾排序，就是按某個增量值對數據進行分組，每組單獨排序好后，再縮小這個增量，然后按新增量對數據分組后每個分組再各自排序。最終增加縮小到1的時候，排序結束。所以希爾排序又叫縮小增量排序(Diminishing Increment Sort)

關于增量
最佳增量值的選擇其實是個數學難題，有興趣的可以自己搜下相關資料。
常用的增量有 n/2(這個又叫希爾增量)、n/3、2^k-1(hibbard增量)等，實際使用中稍微改版增量也可能使排序的性能產生很大的波動。
比如使用n/2的增量，就是初始增量就是 length/2 ,第二輪分組時就再除2：length/4，直至增量值變成1

流程
假設有個數組：[8,12,6,33,12,5,4,94,63,23,75,22,43,27,46]，以n/2為增量，那么整個排序流程就是這樣的：

復雜度
不同增量復雜度不同。n/2時平均的時間復雜度為O(n^2)。
相較直接插入排序，希爾排序減少了比較和交換的次數，在中小規模的排序中，性能表現較好。但隨著數據量增大，希爾排序與其他更好的排序算法（快排、堆排、并歸等）仍有較大差距。

代碼

package main

import (
    "fmt"
    "time"
    "math/rand"
)

func main() {
    var length = 15
    var list []int

    // 以時間戳為種子生成隨機數，保證每次運行數據不重復
    r := rand.New(rand.NewSource(time.Now().UnixNano()))
    for i := 0; i < length; i++ {
        list = append(list, int(r.Intn(1000)))
    }
    fmt.Println(list)

    // 這里就以n/2為增量z
    gap := 2
    step := length / gap

    for step >= 1 {
        // 這里按步長開始每個分組的排序
        for i := step; i < length; i++ {
            // 將按步長分組的子隊列用直接插入排序算法進行排序
            insertionSortByStep(list, step)
        }
        // 完成一輪后再次縮小增量
        step /= gap

        // 輸出每輪縮小增量各組排序后的結果
        fmt.Println(list)
    }
}

// 這里把上篇直接選擇排序的算法抽出來，并將步長從1改成step
func insertionSortByStep(tree []int, step int) {
    for i := step; i < len(tree); i++ {
        for j := i; j >= step && tree[j] < tree[j-step]; j -= step {
            tree[j], tree[j-step] = tree[j-step], tree[j]
        }
    }
}

運行結果