溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

[golang] 數(shù)據(jù)結(jié)構(gòu)-希爾排序

發(fā)布時間:2020-05-19 22:03:22 來源:網(wǎng)絡(luò) 閱讀:973 作者:NicoChen 欄目:編程語言

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

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

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

流程
假設(shè)有個數(shù)組:[8,12,6,33,12,5,4,94,63,23,75,22,43,27,46],以n/2為增量,那么整個排序流程就是這樣的:
[golang] 數(shù)據(jù)結(jié)構(gòu)-希爾排序

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

代碼

package main

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

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

    // 以時間戳為種子生成隨機數(shù),保證每次運行數(shù)據(jù)不重復(fù)
    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

        // 輸出每輪縮小增量各組排序后的結(jié)果
        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]
        }
    }
}

運行結(jié)果
[golang] 數(shù)據(jù)結(jié)構(gòu)-希爾排序

向AI問一下細(xì)節(jié)

免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI