forked from greyireland/algorithm-pattern
-
Notifications
You must be signed in to change notification settings - Fork 218
Expand file tree
/
Copy pathheap_sort.go
More file actions
47 lines (46 loc) · 1.1 KB
/
heap_sort.go
File metadata and controls
47 lines (46 loc) · 1.1 KB
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
package sort
func HeapSort(a []int) []int {
// 1、无序数组a
// 2、将无序数组a构建为一个大根堆
for i := len(a)/2 - 1; i >= 0; i-- {
sink(a, i, len(a))
}
// 3、交换a[0]和a[len(a)-1]
// 4、然后把前面这段数组继续下沉保持堆结构，如此循环即可
for i := len(a) - 1; i >= 1; i-- {
// 从后往前填充值
swap(a, 0, i)
// 前面的长度也减一
sink(a, 0, i)
}
return a
}
func sink(a []int, i int, length int) {
for {
// 左节点索引(从0开始，所以左节点为i*2+1)
l := i*2 + 1
// 有节点索引
r := i*2 + 2
// idx保存根、左、右三者之间较大值的索引
idx := i
// 存在左节点，左节点值较大，则取左节点
if l < length && a[l] > a[idx] {
idx = l
}
// 存在有节点，且值较大，取右节点
if r < length && a[r] > a[idx] {
idx = r
}
// 如果根节点较大，则不用下沉
if idx == i {
break
}
// 如果根节点较小，则交换值，并继续下沉
swap(a, i, idx)
// 继续下沉idx节点
i = idx
}
}
func swap(a []int, i, j int) {
a[i], a[j] = a[j], a[i]
}