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

package main

import "fmt"

// 调整堆

func adjustHeap(array []int, currentIndex int, maxLength int) {

    var noLeafValue = array[currentIndex] // 当前非叶子节点

    // j 指向左孩子

    // 当前非叶子节点的左节点为：2 * currentIndex + 1

    for j := 2*currentIndex + 1; j <= maxLength; j = currentIndex*2 + 1 {

        if j < maxLength && array[j] < array[j+1] { // 如果有右孩子，且左孩子比右孩子小

            j++ // j 指向右孩子

        }

        if noLeafValue >= array[j] {

            break // 非叶子节点大于孩子节点，跳过不交换

        }

        array[currentIndex] = array[j] // 移动到当前节点的父节点

        currentIndex = j               // j 指向交换后的新位置，继续向下比较

    }

    array[currentIndex] = noLeafValue // 放在合适的位置

}

// 初始化堆

func createHeap(array []int, length int) {

    // 建堆

    for i := length / 2; i >= 0; i-- {

        adjustHeap(array, i, length-1)

    }

}

func heapSort(array []int, length int) {

    for i := length - 1; i > 0; i-- {

        array[0], array[i] = array[i], array[0]

        adjustHeap(array, 0, i-1)

    }

}

func main() {

    var unsorted = []int{1, 7, 9, 2, 4, 6, 3, 5, 8}

    var length = len(unsorted)

    fmt.Println("建堆之前：")

    for i := 0; i < length; i++ {

        fmt.Printf("%d,", unsorted[i])

    }

    fmt.Println()

    fmt.Println("建堆之后：")

    createHeap(unsorted, length)

    for i := 0; i < length; i++ {

        fmt.Printf("%d,", unsorted[i])

    }

    fmt.Printf("\n堆排序之后: \n")

    heapSort(unsorted, length)

    for i := 0; i < length; i++ {

        fmt.Printf("%d,", unsorted[i])

    }

}