堆排序 - Mohuishou

注：本文已发布超过一年，请注意您所使用工具的相关版本是否适用

说明

堆积排序：是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

步骤

建堆，建堆是不断调整堆的过程，从 len/2 处开始调整，一直到第一个节点，此处 len 是堆中元素的个数。建堆的过程是线性的过程，从 len/2 到 0 处一直调用调整堆的过程，相当于 o(h1)+o(h2)…+o(hlen/2) 其中 h 表示节点的深度，len/2 表示节点的个数，这是一个求和的过程，结果是线性的 O(n)。
调整堆：调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。利用的思想是比较节点 i 和它的孩子节点 left(i),right(i)，选出三者最大(或者最小)者，如果最大（小）值不是节点 i 而是它的一个孩子节点，那边交互节点 i 和该节点，然后再调用调整堆过程，这是一个递归的过程。调整堆的过程时间复杂度与堆的深度有关系，是 lgn 的操作，因为是沿着深度方向进行调整的。
堆排序：堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，将前面 len-1 个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。堆排序过程的时间复杂度是 O(nlgn)。因为建堆的时间复杂度是 O(n)（调用一次）；调整堆的时间复杂度是 lgn，调用了 n-1 次，所以堆排序的时间复杂度是 O(nlgn)[2]

注意: 根节点在数组当中存放的位置是 0，所以第 i 个节点的左孩子是 2i+1,右孩子是 2i+2

实现

package HeapSort

import (
	"fmt"
)

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

	for i := LEN - 1; i > 0; i-- {
		arr[i], arr[0] = arr[0], arr[i]
		HeapAjust(arr, 0, i)
	}
}

//HeapAjust 堆调整
func HeapAjust(arr []int, start int, length int) {
	tmp := arr[start]
	for i := 2*start + 1; i < length; i = i * 2 {
		if i+1 < length && arr[i] < arr[i+1] {
			i++
		}
		if tmp > arr[i] {
			break
		}
		arr[start] = arr[i]
		start = i
	}
	arr[start] = tmp
}