Golang堆排序的實現步驟如下:
heapify
用于將給定的數組或切片轉換為一個最大堆。最大堆的定義是父節點的值大于或等于其子節點的值。func heapify(arr []int, n int, i int) {
largest := i // 將當前節點標記為最大值
left := 2*i + 1 // 左子節點的索引
right := 2*i + 2 // 右子節點的索引
// 如果左子節點存在且大于根節點,則將最大節點的索引更新為左子節點
if left < n && arr[left] > arr[largest] {
largest = left
}
// 如果右子節點存在且大于根節點,則將最大節點的索引更新為右子節點
if right < n && arr[right] > arr[largest] {
largest = right
}
// 如果最大節點的索引不是根節點,則將最大節點和根節點交換,并遞歸地對交換后的子樹進行堆化
if largest != i {
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
}
}
heapSort
來執行堆排序。func heapSort(arr []int) {
n := len(arr)
// 構建最大堆(初始化堆)
for i := n/2 - 1; i >= 0; i-- {
heapify(arr, n, i)
}
// 逐個提取堆中的元素,并進行堆排序
for i := n - 1; i >= 0; i-- {
// 將當前根節點(最大值)與數組的最后一個元素交換
arr[0], arr[i] = arr[i], arr[0]
// 重新構建最大堆,但不包括已經排序的元素
heapify(arr, i, 0)
}
}
heapSort
函數來對給定的數組進行堆排序。func main() {
arr := []int{12, 11, 13, 5, 6, 7}
heapSort(arr)
fmt.Println("排序后的數組:", arr)
}
這樣就完成了使用Golang實現堆排序的過程。輸出結果將會是[5 6 7 11 12 13]
。