Go語言數(shù)據(jù)結構之希爾排序示例詳解
希爾排序
在插入排序中，在待排序序列的記錄個數(shù)比較少，而且基本有序，則排序的效率較高。
1959 年，Donald Shell 從“減少記錄個數(shù)” 和 “基本有序” 兩個方面對直接插入排序進行了改進，提出了希爾排序算法。
希爾排序又稱為“縮小增量排序”。即將待排序記錄按下標的一定增量分組（減少記錄個數(shù)），對每組記錄使用直接插入排序算法排序（達到基本有序）；
隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1，整個序列基本有序，再對全部記錄進行一次直接插入排序。
算法思想
Shell 排序是一種高效的排序算法，基于插入排序算法。這種算法避免了插入排序中的大量移動，如果較小的值在最右邊，就必須移到最左邊。較小的值在最右邊，必須移到最左邊。
算法步驟：
- 設待排序的記錄存儲在數(shù)組
array[1...n]中，增量序列為{g1, g2, ..., gt},n>g1>g2>...>gt=1。 - 第一趟增量 g1, 所有間隔為 g1 的記錄分在一組，對每組記錄進行插入排序。
- 第二趟取增量 g2，所有間隔為 g2 的記錄分在一組，對每組記錄進行插入排序。
- 依次進行下去，直到所取增量 gt = 1，所有記錄在一組中進行插入排序。
圖解算法
假設我們有一個數(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])
}
}
運行結果：
[Running] go run "e:\Coding Workspaces\LearningGoTheEasiestWay\Go 數(shù)據(jù)結構\希爾排序\main.go"
1
2
3
4
5
6
7
總結
空間復雜度： 希爾排序在分組進行插入排序時使用了一個輔助空間 j，空間復雜度為 O(1)O(1)O(1)
穩(wěn)定性： 希爾排序的分組導致不同組間的相同數(shù)字可能會調(diào)換位置，所以希爾排序是不穩(wěn)定的排序算法。
以上就是Go語言數(shù)據(jù)結構之希爾排序示例詳解的詳細內(nèi)容，更多關于Go 數(shù)據(jù)結構希爾排序的資料請關注腳本之家其它相關文章！
相關文章
本文主要介紹了golang函數(shù)的返回值實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-03-03
golang interface判斷為空nil的實現(xiàn)代碼
這篇文章主要介紹了golang interface判斷為空nil的實現(xiàn)代碼，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-04-04
這篇文章主要介紹了golang控制結構select機制及使用示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-10-10
select語句是Go語言中用于處理多個通道操作的關鍵字,它允許你在多個通道上進行非阻塞的選擇操作,本文就詳細介紹一下如何使用,感興趣的可以了解一下2023-09-09
go語言實現(xiàn)Elasticsearches批量修改查詢及發(fā)送MQ操作示例
這篇文章主要為大家介紹了go語言實現(xiàn)Elasticsearches批量修改查詢及發(fā)送MQ操作示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-04-04
這篇文章主要為大家介紹了Go語言編碼效率提升技巧詳解,學會了從此拒絕加班,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-12-12
Gin 框架快速創(chuàng)建靜態(tài)文件下載Web服務
本文主要介紹了Gin 框架快速創(chuàng)建靜態(tài)文件下載Web服務，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-12-12
這篇文章主要介紹了go語言使用scp的方法,實例分析了go語言調(diào)用scp命令的使用技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-03-03
在學習操作系統(tǒng)的時候，我們應該都學習過臨界區(qū)、互斥鎖這些概念，用于在并發(fā)環(huán)境下保證狀態(tài)的正確性。在?Go語言?里面互斥鎖是?sync.Mutex?，我們本篇文章就來學習下為什么要使用互斥鎖、如何使用互斥鎖，以及使用時的常見問題2022-10-10
Golang操作MySql數(shù)據(jù)庫的完整步驟記錄
這篇文章主要給大家介紹了關于Golang操作MySql數(shù)據(jù)庫的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-11-11