堆排序(go实现)

package main

import "fmt"

//初始化堆
var arr = []int{0, 10, 100, 2, 45, 95, 1, 5, 8888}

//初始化堆
func initHeap(arr []int, n int) {
    for i := n / 2; i >= 1; i-- {
        heapify(arr, n, i)
    }
}

//堆化
func heapify(heap []int, n int, i int) {
    for {
        maxPos := i
        //比左边的子元素大
        if i*2 <= n && heap[i] < heap[i*2] {
            maxPos = i * 2
        }
        //比右边的子元素大
        if i*2+1 <= n && heap[maxPos] < heap[i*2+1] {
            maxPos = i*2 + 1
        }
        //maxPos == i 说明比左右子元素都小,跳出循环
        if maxPos == i {
            break
        }
        //交换父元素和子元素的值
        heap[i], heap[maxPos] = heap[maxPos], heap[i]
        i = maxPos
    }
}

//堆排序
func sort(arr []int) {
    n := len(arr) - 1
    initHeap(arr, n)
    k := n
    for k > 1 {
        arr[1], arr[k] = arr[k], arr[1]
        k--
        heapify(arr, k, 1)
    }
}

func main() {
    sort(arr)
    fmt.Println(arr)
}