手写堆排序

摘要：本文记录使用go语言实现堆排序

堆的构建

• 堆性质： 对于每个小堆，父节点与两个子节点比较，父节点比左子节点大，也比右子节点大。

有五个数： 1,2,3,4,5 分别进行入栈。过程如下

(1) 堆为空时，元素1 放入堆

(2) 取出元素2，挂到元素1后面

(3) 比较元素2，与父元素元素1，由于元素2 比 元素1 大，所以两个元素交换

(4) 元素3 先放入堆最后

(5) 元素3 比父节点大，与父节点交换

(6) 元素4 放到堆最后

(6) 元素4 比父节点你先把给的和反正都吃了元素1 大，所以把元素4 与 元素1 交换

(7) 元素4 比父节点元素3 大，所以把元素4 与 元素3我 交换

(8) 同理，元素5 先放入堆最后，再分别与父节点比较，直到达到堆性质。

代码实现

package mainimport "fmt"// heapify 将父节点与子节点比较，并将最大值放到父节点(用于实现大顶堆)
func heapify(arr []int, n, i int) {if i >= n {// 递归退出条件return}// 找出最大的var prarent = ivar max = prarentvar c1 = prarent*2 + 1var c2 = prarent*2 + 2if c1 < n && arr[c1] > arr[max] {max = c1}if c2 < n && arr[c2] > arr[max] {max = c2}// 如果最大节点不是父节点，则最大的节点与父节点交换if max != prarent {arr[max], arr[i] = arr[i], arr[max]// 递归的进行 heapifyheapify(arr, n, max)}}// heapInit 遍历依次heapify
func heapInit(arr []int, n int) {for i := 0; i < n; i++ {heapify(arr, n, i)}
}// 利用堆实现排序
func heapSort(heapTree []int) {if len(heapTree) == 0 {return}var heapSize = len(heapTree)for heapSize > 0 {// 将堆顶元素放到最后heapTree[0], heapTree[heapSize-1] = heapTree[heapSize-1], heapTree[0]heapSize--// 对堆顶元素执行heapifyheapify(heapTree, heapSize, 0)}
}func main() {arr := []int{2, 1, 10, 3, 5, 4}heapInit(arr, 6)fmt.Println(arr) // [10 5 4 3 1 2]heapSort(arr)fmt.Println(arr) // 1 2 3 4 5 10arr = []int{3, 3, 4, 2, 1}heapInit(arr, 5)fmt.Println(arr)heapSort(arr) // [4 3 3 2 1]fmt.Println(arr) // 1 2 3 3 4}