堆排序之golang实现
2021-07-01 23:03
标签：import port build pack func 使用数组 pre ack adjust 主要是理解思路，思路有了代码则是水到渠成。 堆排序实际是数组排序，使用数组的下标构造成一个二叉树，想法很有意思。 加入有数组a，那可以把a[0]视为根节点，它的子节点为a[2*0+1]，a[2*0+2]，即对于任何一个节点a[i]，则有子节点a[2*i+1]和a[2*i+2]。 1. 构建一个大顶堆，构建成功后a[0]便是最大的。 2. 之后交换a[0]和a[len(a)-1] 3. 然后在调整a[:len(a)-2]（把a[len(a)-1]排除在外）为大顶堆 4. 重复上面的步骤 5. 得到有序数组 堆排序之golang实现 标签：import port build pack func 使用数组 pre ack adjust 原文地址：https://www.cnblogs.com/zcqkk/p/9636325.htmlpackage main
import (
"fmt"
)
func adjustHeap(a []int, pos int, lenght int) {
for {
// 计算孩子位置
child := pos*2 + 1
// 检查孩子是否越界
if child >= (lenght - 1) {
break
}
// 找出孩子中较大的那个
if a[child+1] > a[child] {
child++
}
// 检查孩子是否大于父亲，如果大于则交换
if a[pos] = 0; i-- {
adjustHeap(a, i, len(a))
}
}
func heapSort(a []int) {
// 构建大顶堆
buildHeap(a)
fmt.Println("buildHeap over:", a)
fmt.Println("===============================")
// 首尾交换，重新构建大顶堆
for i := len(a) - 1; i >= 0; i-- {
a[0], a[i] = a[i], a[0]
adjustHeap(a, 0, i)
}
}
func main() {
num := []int{98, 48, 777, 63, 57, 433, 23, 1112, 1}
heapSort(num)
fmt.Println("heap sort over:", num)
}