Go語言數(shù)據(jù)結(jié)構(gòu)之希爾排序示例詳解
希爾排序
在插入排序中,在待排序序列的記錄個數(shù)比較少,而且基本有序,則排序的效率較高。
1959 年,Donald Shell 從“減少記錄個數(shù)” 和 “基本有序” 兩個方面對直接插入排序進(jìn)行了改進(jìn),提出了希爾排序算法。
希爾排序又稱為“縮小增量排序”。即將待排序記錄按下標(biāo)的一定增量分組(減少記錄個數(shù)),對每組記錄使用直接插入排序算法排序(達(dá)到基本有序);
隨著增量逐漸減少,每組包含的關(guān)鍵詞越來越多,當(dāng)增量減至1,整個序列基本有序,再對全部記錄進(jìn)行一次直接插入排序。
算法思想
Shell 排序是一種高效的排序算法,基于插入排序算法。這種算法避免了插入排序中的大量移動,如果較小的值在最右邊,就必須移到最左邊。較小的值在最右邊,必須移到最左邊。
算法步驟:
- 設(shè)待排序的記錄存儲在數(shù)組
array[1...n]
中,增量序列為{g1, g2, ..., gt}
,n>g1>g2>...>gt=1
。 - 第一趟增量 g1, 所有間隔為 g1 的記錄分在一組,對每組記錄進(jìn)行插入排序。
- 第二趟取增量 g2,所有間隔為 g2 的記錄分在一組,對每組記錄進(jìn)行插入排序。
- 依次進(jìn)行下去,直到所取增量 gt = 1,所有記錄在一組中進(jìn)行插入排序。
圖解算法
假設(shè)我們有一個數(shù)組: [7, 4, 3, 5, 2, 1, 6]
:
第一次希爾排序間隔為3時:
第二次希爾排序間隔為2時:
第三次希爾排序間隔為1時:
Go 代碼實現(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é)果:
[Running] go run "e:\Coding Workspaces\LearningGoTheEasiestWay\Go 數(shù)據(jù)結(jié)構(gòu)\希爾排序\main.go"
1
2
3
4
5
6
7
總結(jié)
空間復(fù)雜度: 希爾排序在分組進(jìn)行插入排序時使用了一個輔助空間 j
,空間復(fù)雜度為 O(1)O(1)O(1)
穩(wěn)定性: 希爾排序的分組導(dǎo)致不同組間的相同數(shù)字可能會調(diào)換位置,所以希爾排序是不穩(wěn)定的排序算法。
以上就是Go語言數(shù)據(jù)結(jié)構(gòu)之希爾排序示例詳解的詳細(xì)內(nèi)容,更多關(guān)于Go 數(shù)據(jù)結(jié)構(gòu)希爾排序的資料請關(guān)注腳本之家其它相關(guān)文章!
- go?sync?Waitgroup數(shù)據(jù)結(jié)構(gòu)實現(xiàn)基本操作詳解
- Golang迭代如何在Go中循環(huán)數(shù)據(jù)結(jié)構(gòu)使用詳解
- Go 語言數(shù)據(jù)結(jié)構(gòu)之雙鏈表學(xué)習(xí)教程
- Go 數(shù)據(jù)結(jié)構(gòu)之堆排序示例詳解
- Go語言數(shù)據(jù)結(jié)構(gòu)之選擇排序示例詳解
- Go語言數(shù)據(jù)結(jié)構(gòu)之插入排序示例詳解
- go數(shù)據(jù)結(jié)構(gòu)和算法BitMap原理及實現(xiàn)示例
- Go?語言數(shù)據(jù)結(jié)構(gòu)如何實現(xiàn)抄一個list示例詳解
相關(guān)文章
golang interface判斷為空nil的實現(xiàn)代碼
這篇文章主要介紹了golang interface判斷為空nil的實現(xiàn)代碼,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2021-04-04golang控制結(jié)構(gòu)select機(jī)制及使用示例詳解
這篇文章主要介紹了golang控制結(jié)構(gòu)select機(jī)制及使用示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-10-10go語言實現(xiàn)Elasticsearches批量修改查詢及發(fā)送MQ操作示例
這篇文章主要為大家介紹了go語言實現(xiàn)Elasticsearches批量修改查詢及發(fā)送MQ操作示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-04-04Gin 框架快速創(chuàng)建靜態(tài)文件下載Web服務(wù)
本文主要介紹了Gin 框架快速創(chuàng)建靜態(tài)文件下載Web服務(wù),文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下2021-12-12Golang操作MySql數(shù)據(jù)庫的完整步驟記錄
這篇文章主要給大家介紹了關(guān)于Golang操作MySql數(shù)據(jù)庫的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11