您好,登錄后才能下訂單哦!
除了上篇介紹的二分插入排序,還有這次介紹的希爾排序(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為增量,那么整個排序流程就是這樣的:
復(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é)果
免責(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)容。