时间复杂度：O(n log n)

    • 最好：O(n log n)
    • 最坏：O(n log n)

    空间复杂度：O(1)

    • 只需要一个额外空间用于数据交换

    原理
    堆排序（Heaps Sort）是指利用堆这种数据结构所设计的一种不稳定排序算法。
    堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
    堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

    • 大顶堆（大根堆）：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
    • 小顶堆（小根堆）：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

    实现

    1. 创建一个堆，将数据放在堆中存储。
    2. 按大顶堆构建堆，其中大顶堆的一个特性是数据将被从大到小取出，将取出的数据元素按照相反的顺序进行排列，数据元素就完成了排序。
    3. 然后从左到右，从上到下进行调整，构造出大顶堆。
    4. 入堆完成之后，将堆顶元素取出，将末尾元素置于堆顶，重新调整结构，使其满足堆定义。 ```go

    func heapSort(slice []int) []int { if len(slice) < 2 { return slice }

    1. // 从数组内倒数第一个根节点开始，将数组堆化
    2. for i := len(slice) / 2; i >= 0; i-- {
    3.     maxHeapify(slice, i, len(slice)-1)
    4. }
    6. // 1.将堆顶数据与尾部数据交换
    7. // 2.从新堆化，将堆顶数据下压
    8. end := len(slice) - 1
    9. for end > 0 {
    10.     slice[0], slice[end] = slice[end], slice[0]
    11.     end--
    12.     maxHeapify(slice, 0, end)
    13. }
    15. return slice

    }

    // 小顶堆 堆化 func minHeapify(slice []int, root, end int) { for { min := root l := (root << 1) + 1 if l <= end && slice[l] < slice[min] { min = l }

    1.     r := l + 1
    2.     if r <= end && slice[r] < slice[min] {
    3.         min = r
    4.     }
    6.     if min == root {
    7.         break
    8.     }
    10.     slice[root], slice[min] = slice[min], slice[root]
    11.     root = min
    12. }

    }

    // 大顶堆 堆化 func maxHeapify(slice []int, root, end int) { for { max := root l := (root << 1) + 1 if l <= end && slice[l] > slice[max] { max = l }

    1.     r := l + 1
    2.     if r <= end && slice[r] > slice[max] {
    3.         max = r
    4.     }
    6.     if max == root {
    7.         break
    8.     }
    10.     slice[root], slice[max] = slice[max], slice[root]
    11.     root = max
    12. }

    } ```