堆排序，go实现

heapsort.go

// HeapSort project main.go
package main

import (
	"fmt"
)

func HeapSort(s []int) {
	length := len(s) - 1 //s[0]不用，实际元素数量和最后一个元素的角标都为length
	//构造堆
	//节点的父节点，角标为length/2
	for k := length / 2; k >= 1; k-- {
		sift(s, k, length)
	}
	//排序
	for length > 1 {
		swap(s, 1, length) //将大的放在数组后面，升序排序
		length--
		sift(s, 1, length)
	}
}

//调整堆
func sift(s []int, k, length int) {
	for {
		i := 2 * k
		if i > length { //保证该节点是非叶子节点
			break
		}
		if i < length && s[i+1] > s[i] { //选择较大的子节点
			i++
		}
		if s[k] >= s[i] {
			break
		}
		swap(s, k, i)
		k = i
	}
}

func swap(s []int, i int, j int) {
	s[i], s[j] = s[j], s[i]
}

func main() {
	s := []int{-1, 2, 8, 4, 5, 9, 1, 7, 66}
	fmt.Println(s[1:])
	HeapSort(s)
	fmt.Println(s[1:])
}