Go語言數據結構之希爾排序示例詳解
希爾排序
在插入排序中,在待排序序列的記錄個數比較少,而且基本有序,則排序的效率較高。
1959 年,Donald Shell 從“減少記錄個數” 和 “基本有序” 兩個方面對直接插入排序進行瞭改進,提出瞭希爾排序算法。
希爾排序又稱為“縮小增量排序”。即將待排序記錄按下標的一定增量分組(減少記錄個數),對每組記錄使用直接插入排序算法排序(達到基本有序);
隨著增量逐漸減少,每組包含的關鍵詞越來越多,當增量減至1,整個序列基本有序,再對全部記錄進行一次直接插入排序。
算法思想
Shell 排序是一種高效的排序算法,基於插入排序算法。這種算法避免瞭插入排序中的大量移動,如果較小的值在最右邊,就必須移到最左邊。較小的值在最右邊,必須移到最左邊。
算法步驟:
- 設待排序的記錄存儲在數組
array[1...n]
中,增量序列為{g1, g2, ..., gt}
,n>g1>g2>...>gt=1
。 - 第一趟增量 g1, 所有間隔為 g1 的記錄分在一組,對每組記錄進行插入排序。
- 第二趟取增量 g2,所有間隔為 g2 的記錄分在一組,對每組記錄進行插入排序。
- 依次進行下去,直到所取增量 gt = 1,所有記錄在一組中進行插入排序。
圖解算法
假設我們有一個數組: [7, 4, 3, 5, 2, 1, 6]
:
第一次希爾排序間隔為3時:
第二次希爾排序間隔為2時:
第三次希爾排序間隔為1時:
Go 代碼實現:
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 數據結構\希爾排序\main.go"
1
2
3
4
5
6
7
總結
空間復雜度: 希爾排序在分組進行插入排序時使用瞭一個輔助空間 j
,空間復雜度為 O(1)O(1)O(1)
穩定性: 希爾排序的分組導致不同組間的相同數字可能會調換位置,所以希爾排序是不穩定的排序算法。
以上就是Go語言數據結構之希爾排序示例詳解的詳細內容,更多關於Go 數據結構希爾排序的資料請關註WalkonNet其它相關文章!