Algorithm of Heapsort

main.go

package main

import "fmt"

func main() {
	var nums []int = []int{57, 40, 38, 11, 13, 34, 48, 75, 6, 19, 9, 7}
	heapsort(nums)
	fmt.Println(nums)
}

func heapsort(nums []int) {
	sift(nums, len(nums))

	for i := len(nums) - 1; i > 0; i-- {
		var tmp int = nums[0]
		nums[0] = nums[i]
		nums[i] = tmp

		sift(nums, i)
	}
}

func sift(nums []int, length int) {
	for i := length/2 - 1; i >= 0; i-- {
		var leftI int = 2*i + 1
		var rightI int = 2*i + 2
		if leftI < length && nums[leftI] > nums[i] {
			var tmp int = nums[i]
			nums[i] = nums[leftI]
			nums[leftI] = tmp
		}
		if rightI < length && nums[rightI] > nums[i] {
			var tmp int = nums[i]
			nums[i] = nums[rightI]
			nums[rightI] = tmp
		}
	}
}

参考解释（下述两篇解释不是非常直观，难以理解，凑合看看）：
https://juejin.cn/post/6904810712632295432
https://zhuanlan.zhihu.com/p/45725214

要点围绕：

• 大顶堆调整中的非叶子节点循环最大值比较筛选，每次最大值往顶点摆放（length/2-1 ~ 0 所有非叶子节点范围）
• 每次调整完毕之后顶点为最大值，交换 0 与 length - 1 并排除 length - 1 得出新的堆重复调整步骤