Go語言堆排序的實現步驟如下:
adjustHeap
,該函數接受三個參數:待調整的切片 arr
,當前需要調整的節點的下標 i
,以及堆的大小 length
。adjustHeap
函數中,首先獲取當前節點的值,然后計算出其左子節點和右子節點的下標。maxIndex
。maxIndex
所對應的子節點的值,則交換兩者的值,并遞歸調用 adjustHeap
函數,以保證堆的性質。adjustHeap
函數來從最后一個非葉子節點開始進行堆調整。adjustHeap
函數對堆頂元素進行調整,以保持堆的性質。下面是具體的代碼實現:
package main
import "fmt"
func adjustHeap(arr []int, i, length int) {
temp := arr[i]
for k := i*2 + 1; k < length; k = k*2 + 1 {
if k+1 < length && arr[k] < arr[k+1] {
k++
}
if arr[k] > temp {
arr[i] = arr[k]
i = k
} else {
break
}
}
arr[i] = temp
}
func heapSort(arr []int) {
length := len(arr)
for i := length/2 - 1; i >= 0; i-- {
adjustHeap(arr, i, length)
}
for i := length - 1; i > 0; i-- {
arr[0], arr[i] = arr[i], arr[0]
adjustHeap(arr, 0, i)
}
}
func main() {
arr := []int{9, 8, 7, 6, 5, 4, 3, 2, 1}
heapSort(arr)
fmt.Println(arr)
}
輸出結果為 [1 2 3 4 5 6 7 8 9]
,表示已經成功對輸入的序列進行了堆排序。