# go 堆排序
## 堆排序
堆排序本身需要将数组看作一个完全二叉树，然后动态的将这棵树维护成一个 大根堆或小根堆
## code
```go
package main
import"fmt"
func main() {
// 要将数组看作一个完全二叉树
arrs := []int{3,2,7,5,9,1,7,8,4,6,5,7}
fmt.Printf("before arr is: %v\n", arrs)
heapSort(arrs)
fmt.Printf("after arr is: %v\n", arrs)
}
func heapSort(arrs []int) {
l := len(arrs)
initHeap(arrs, l)
// 当前已经建立一个大根堆
// 开始排序
for i := l-1; i>0; i-- {
// 取出堆顶元素
arrs[0], arrs[i] = arrs[i], arrs[0]
// 此时堆顶已经不再是最大的元素，需要对整个堆做一次sink
// 待排序的堆是arrs[:l]
l --
sink(arrs, 0, l)
}
}
// 初始化一个堆
func initHeap(arrs []int, l int) {
for i := l / 2; i >= 0; i-- {
sink(arrs, i, l)
}
}
// sink可以生成一个以i为根节点的大根堆
func sink(arrs []int, i, l int) {
// 左右子孩子
left, right := 2*i + 1, 2*i + 2
// largest用来记录i和两个子孩子中最大的那个
largest := i
if left < l && arrs[left] > arrs[largest] {
largest = left
}
if right < l && arrs[right] > arrs[largest] {
largest = right
}
if largest != i {
arrs[largest], arrs[i] = arrs[i], arrs[largest]
// 此时 arrs[i] 已经是 i, left, right三个里最大的了
// largest的值变化了，要从新sink 以largest为root的堆
sink(arrs, largest, l)
}
}
```
## 结果
before arr is: [3 2 7 5 9 1 7 8 4 6 5 7]
after arr is: [1 2 3 4 5 5 6 7 7 7 8 9]
有疑问加站长微信联系（非本文作者））
