FilesExpand file tree

master

/

heap_sort.go

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

47 lines (46 loc) · 1.1 KB

master

/

heap_sort.go

Copy path

Top

File metadata and controls

• Code
• Blame

47 lines (46 loc) · 1.1 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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]

}