堆排序

说明

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

步骤

  • 建堆,建堆是不断调整堆的过程,从 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

示例

示例图片

实现

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
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
}

关注我获取更新

wechat
知乎
开发者头条
github

猜你喜欢


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议,转载请注明出处,禁止全文转载