堆排序

参考链接：https://www.cnblogs.com/chengxiao/p/6129630.html

//堆排序
func headSort(arr []int) {
	length := len(arr)
	for i := length/2 - 1; i >= 0; i-- {
		heap(arr, i, length)
	}

	fmt.Println(arr)
	for j := length - 1; j > 0; j-- {
		arr[0], arr[j] = arr[j], arr[0]
		heap(arr, 0, j)
	}
}

func heap(arr []int, start int, length int) {
	temp := arr[start]
	fmt.Println(start, length, arr)
	for i := start*2 + 1; i < length; i = i*2 + 1 {
		if i+1 < length && arr[i] < arr[i+1] {
			i++
		}
		if arr[i] > temp {
			arr[start], start = arr[i], i
		} else {
			break
		}
	}
	arr[start] = temp
}