堆排序

堆排序

堆通常是一个可以被看做一棵树的数组对象。堆的实现通过构造二叉堆(binary heap),实为二叉树的一种

  • 任意节点小于(或大于)它的所有后裔,最小元(或最大元)在堆的根上(堆序性)。
  • 堆总是一棵完全树。即除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。

最大堆:根节点最大
最小堆:根节点最小

思路

利用堆的这个特性,可以知道根节点一定是最大值。

将根节点与最后一个叶子节点互换。每次使用n-i个节点继续多次即可(i 为已经交换过的次数)

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class HeapSort(private val node: IntArray) {
fun sort() {
for (i in 1 until node.size) {
// 构建确保根节点一定最大的堆
buildHeap(node.size - i)
// 根节点与最后一个叶子节点交换
swap(node.size - i)
}
println(node.contentToString())
}

private fun swap(lastIndex: Int) {
val temp = node[0]
node[0] = node[lastIndex]
node[lastIndex] = temp
}

private fun buildHeap(lastIndex: Int) {
/*
从最后一个父节点开始,使其一定大于其子节点。
再继续倒数第二个父节点依然保证其比子节点大
不需要关心下调的节点是否比子节点大,因为上调的节点一定是最大值,我们只需要找出最大值即可。
*/
for (i in (lastIndex - 1) / 2 downTo 0) {
var child = i * 2 + 1
val temp = node[i]
// 存在右节点且比左节点大
if (child + 1 <= lastIndex && node[child] < node[child + 1]) {
child++
}
// 若子节点比父节点大,则父节点下调
if (node[i] < node[child]) {
node[i] = node[child]
node[child] = temp
}
}
}
}

fun main() {
HeapSort(intArrayOf(1, 3, 2, 6, 5, 7, 8, 9, 10, 30)).sort()
}