堆排序

排序

说明

建最大堆后反复把最大值放到末尾；时间 O(n log n)、额外空间 O(1)。

分析

先自底向上建立最大堆，根节点就是当前最大值。将根与末尾交换后缩小堆，再向下调整新的根，直到全部元素有序。

图解推演

[3,1,2] 已满足最大堆。把根 3 换到末尾后，堆区缩为 [2,1]；再把 2 换到末尾，结果 [1,2,3]。堆区右侧是已排序后缀，调整时绝不能把它纳入堆大小。自底向上建堆为 O(n)，后续 n 次取最大值决定总时间 O(n log n)。

查看图表代码

适用前提与边界

它有稳定的 O(n log n) 时间上界且原地排序，但相等元素的顺序不保留。

示例输入与调用

a := []int{3, 1, 2}
	HeapSort(a)
	fmt.Println(a)

运行输出

[1 2 3]

完整 Go 示例

package main

import "fmt"

func HeapSort(a []int) {
	var down func(int, int)
	down = func(i, n int) {
		for 2*i+1 < n {
			c := 2*i + 1
			if c+1 < n && a[c+1] > a[c] {
				c++
			}
			if a[i] >= a[c] {
				break
			}
			a[i], a[c] = a[c], a[i]
			i = c
		}
	}
	for i := len(a)/2 - 1; i >= 0; i-- {
		down(i, len(a))
	}
	for n := len(a); n > 1; n-- {
		a[0], a[n-1] = a[n-1], a[0]
		down(0, n-1)
	}
}

func main() {
	a := []int{3, 1, 2}
	HeapSort(a)
	fmt.Println(a)
}