堆排序

排序简介

堆是一个近似完全二叉树的结构

• 大顶堆， 每个节点的值都大于或等于其他子节点的值， 用于升序排列
• 小顶堆， 每个节点的值都小于或等于其他子节点的值， 用于降序排列

先创建一个小顶堆， 堆首值（最小值）和堆尾互换位置，即找到最小值；再把堆的长度-1，再找出次小值；不断重复这个过程，直到排序完成。

图解参考https://www.cnblogs.com/chengxiao/p/6129630.html

复杂度

• 最佳情况：T(n) = O(nlogn)
• 最坏情况：T(n) = O(nlogn)
• 平均情况：T(n) = O(nlogn)
• 空间复杂度：O(1)
• 稳定性：不稳定
• 排序方式：In-place

golang实现

package main

import "fmt"

func minHeap(root int, end int, c []int)  {
    for  {
        var child = 2*root + 1
        // 判断是否存在child节点
        if child > end {
            break
        }
        // 判断右child是否存在， 如果存在则和另一个同级节点进行比较
        if child+1 <= end && c[child] > c[child+1] {
            child += 1
        }
        if c[root] > c[child] {
            c[root], c[child] = c[child], c[root]
            root = child
        }else {
            break
        }
    }
}

// 降序排序
func HeapSort(c []int)  {
    var n = len(c)-1
    for root := n/2; root >= 0; root-- {
        minHeap(root, n, c)
    }
    fmt.Println("堆构建完成")
    for end := n; end >= 0; end-- {
        if c[0] < c[end] {
            c[0], c[end] = c[end], c[0]
            minHeap(0, end-1, c)
        }
    }
}

func main() {
    arr := []int{33,11,55,7,44,1}
    HeapSort(arr)
    fmt.Println(arr)
}