排序算法Golang实现之堆排序

1.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆。

2.将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端。

3.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序 。

 package sort

//Heap 堆排序
func Heap(nums []int) {
	lenght := len(nums)
	for i := 0; i < lenght; i++ {
		lastlen := lenght - i
		sortMax(nums, lastlen)
		if i < lenght {
			nums[0], nums[lastlen-1] = nums[lastlen-1], nums[0] // 首尾交换
		}
	}
}

func sortMax(arr []int, length int) []int {
	if length <= 1 {
		return arr
	}

	depth := length/2 - 1 // 二叉树深度
	for i := depth; i >= 0; i-- {
		topmax := i // 假定最大位置就在i
		leftchild := 2*i + 1
		rightchild := 2*i + 2

		if leftchild <= length-1 && arr[leftchild] > arr[topmax] { // 防止越过界限
			topmax = leftchild
		}

		if rightchild <= length-1 && arr[rightchild] > arr[topmax] { // 防止越过界限
			topmax = rightchild
		}

		if topmax != i {
			arr[i], arr[topmax] = arr[topmax], arr[i]
		}
	}

	return arr
}