golang 堆排序
堆排序的思想 因为堆的形式是完全二叉树,跟数组的索引形成映射,可以使用数组保存。先构建最大(小)堆,根结点就是最大(小)值,删除根结点之后的节点重新构建堆,依此顺序,即可完成堆排序。
代码实现
SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。package main
import "fmt"
func main() {
a := []int{34, 52, 12, 45, 56, 10, 35}
//fmt.Println(a[:len(a)])
HeapSort2(a)
}
func HeapSort2(a []int) {
length := len(a)
for i:=0; i<length; i++ {
BuildHeap(a[:length-i])
a[0], a[length-i-1] = a[length-i-1], a[0]
fmt.Println(i, a)
}
}
func BuildHeap(a []int) {
pos := len(a)
start := (pos-2)/2
for i:=start; i>=0; i-- {
AdjustHeap(a, i)
}
}
//调整最大堆
func AdjustHeap(a []int, pos int) {
length := len(a)
current := pos
for current < length{
var child int
if 2*current+2 < length{
//有左右节点
if a[2*current+2] >= a[2*current+1] {
child = 2*current+2
} else {
child = 2*current+1
}
} else if 2*current+1 < length {
//只有左节点
child = 2*current+1
} else {
break;
}
if a[current] < a[child] {
a[current], a[child] = a[child], a[current]
current = child
} else {
break;
}
}
}