堆排序基本知识
基本介绍
堆是一个完全二叉树，因此我们可以利用节点的特性去使用一个数组模拟一颗完全二叉树：
- 下标为i的节点的左子节点的下标为
i*2+1, 右子节点的下标为i*2+2 - 下标为i的节点的父节点的下标为(i-1)/2
建立堆的时间复杂度：O(log1) + O(log2) + … + O(logN) 近似于 O(N)，因此建立堆的时间复杂度为O(N)
堆有大根堆以及小根堆，没有规定堆中左子树的根必须大于(或小于)右子树的根。
堆排序的两个基本步骤：(具体说明看代码注释)
- 建堆，循环将数组中的每个数加入堆中（每次都需要heapInsert）
- 不断从堆的最后一个元素交换到堆的头部，然后将堆的长度减小1，再调整堆，每次都需要heapify
具体实现
查看代码
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| func HeapSort(nums []int) []int {
heapSort(nums)
return nums
}
func heapSort(nums []int) {
if nums == nil || len(nums) < 2 {
return
}
for i := 0; i < len(nums); i++ {
heapInsert(nums, i)
}
log.Println("建堆完成--------------->", nums)
heapSize := len(nums)
for heapSize > 0 {
nums[0], nums[heapSize-1] = nums[heapSize-1], nums[0]
heapSize--
heapify(nums, heapSize, 0)
}
}
func heapInsert(nums []int, index int) {
for nums[(index-1)/2] < nums[index] {
nums[index], nums[(index-1)>>1] = nums[(index-1)>>1], nums[index]
index = (index - 1) >> 1
}
}
func heapify(nums []int, heapSize int, index int) {
for i := index; i*2+1 < heapSize; {
left := 2*i + 1
if left+1 < heapSize && nums[left+1] > nums[left] {
left++
}
if nums[i] >= nums[left] {
break
}
nums[i], nums[left] = nums[left], nums[i]
i = left
}
}
|
