Go語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之希爾排序示例詳解

更新時(shí)間：2022年08月26日 16:10:31 作者：宇宙之一粟

這篇文章主要為大家介紹了Go語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之希爾排序示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

希爾排序

在插入排序中，在待排序序列的記錄個(gè)數(shù)比較少，而且基本有序，則排序的效率較高。

1959 年，Donald Shell 從“減少記錄個(gè)數(shù)” 和 “基本有序” 兩個(gè)方面對(duì)直接插入排序進(jìn)行了改進(jìn)，提出了希爾排序算法。

希爾排序又稱(chēng)為“縮小增量排序”。即將待排序記錄按下標(biāo)的一定增量分組（減少記錄個(gè)數(shù)），對(duì)每組記錄使用直接插入排序算法排序（達(dá)到基本有序）；

隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1，整個(gè)序列基本有序，再對(duì)全部記錄進(jìn)行一次直接插入排序。

算法思想

Shell 排序是一種高效的排序算法，基于插入排序算法。這種算法避免了插入排序中的大量移動(dòng)，如果較小的值在最右邊，就必須移到最左邊。較小的值在最右邊，必須移到最左邊。

算法步驟：

設(shè)待排序的記錄存儲(chǔ)在數(shù)組 array[1...n] 中，增量序列為 {g1, g2, ..., gt} , n>g1>g2>...>gt=1 。
第一趟增量 g1, 所有間隔為 g1 的記錄分在一組，對(duì)每組記錄進(jìn)行插入排序。
第二趟取增量 g2，所有間隔為 g2 的記錄分在一組，對(duì)每組記錄進(jìn)行插入排序。
依次進(jìn)行下去，直到所取增量 gt = 1，所有記錄在一組中進(jìn)行插入排序。

圖解算法

假設(shè)我們有一個(gè)數(shù)組： [7, 4, 3, 5, 2, 1, 6] :

第一次希爾排序間隔為3時(shí)：

第二次希爾排序間隔為2時(shí)：

第三次希爾排序間隔為1時(shí)：

Go 代碼實(shí)現(xiàn)：

package main
import "fmt"
func swap(array []int, a int, b int) {
    array[a] = array[a] + array[b]
    array[b] = array[a] - array[b]
    array[a] = array[a] - array[b]
}
func shellSort(array []int, length int) {
    for gap := length / 2; gap > 0; gap = gap / 2 {
        for i := gap; i < length; i++ {
            var j = i
            for {
                if j-gap < 0 || array[j] >= array[j-gap] {
                    break
                }
                swap(array, j, j-gap)
                j = j - gap
            }
        }
    }
}
func main() {
    nums := []int{7, 4, 3, 5, 2, 1, 6}
    length := len(nums)
    shellSort(nums, length)
    for i := 0; i < length; i++ {
        fmt.Println(nums[i])
    }
}

運(yùn)行結(jié)果：