堆排序

时间复杂度：O(logn)

先创建一个堆，然后调整堆，调整过程是将节点和子节点进行比较，将其中最大的值变为父节点，递归调整调整次数lgn,最后将根节点和尾节点交换再n次调整O(nlgn).

算法步骤：

• 创建最大堆或者最小堆

• 调整堆

• 交换首尾节点

手写堆排序

package sort

import "fmt"

func HeapSortMax(arr []int, length int) []int {
    // length := len(arr)
    if length <= 1 {
        return arr
    }
    depth := length/2 - 1 //二叉树深度
    for i := depth; i >= 0; i-- {
        topmax := i //假定最大的位置就在i的位置
        leftchild := 2*i + 1
        rightchild := 2*i + 2
        if leftchild <= length-1 && arr[leftchild] > arr[topmax] { //防止越过界限
            topmax = leftchild
        }
        if rightchild <= length-1 && arr[rightchild] > arr[topmax] { //防止越过界限
            topmax = rightchild
        }
        if topmax != i {
            arr[i], arr[topmax] = arr[topmax], arr[i]
        }
    }
    return arr
}
func HeapSort(arr []int) []int {
    length := len(arr)
    for i := 0; i < length; i++ {
        lastlen := length - i
        HeapSortMax(arr, lastlen)
        if i < length {
            arr[0], arr[lastlen-1] = arr[lastlen-1], arr[0]
        }
    }
    return arr
}

heap

package main

import (
    "container/heap"
    "fmt"
)

// IntHeap 实现 heap.Interface 接口
type IntHeap []int

func (h IntHeap) Len() int {
    return len(h)
}

func (h IntHeap) Less(i, j int) bool {
    // 如果设置 h[i] < h[j] 就是小顶堆，h[i] > h[j] 就是大顶堆
    return h[i] < h[j]
}

func (h IntHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    x := (*h)[len(*h)-1]
    *h = (*h)[:len(*h)-1]
    return x
}

func main() {
    // 创建切片
    h := &IntHeap{2, 1, 5, 6, 4, 3, 7, 9, 8, 0}

    // 初始化小顶堆
    heap.Init(h)
    fmt.Println(*h) // [0 1 3 6 2 5 7 9 8 4]

    // Pop 元素
    fmt.Println(heap.Pop(h).(int)) // 0

    // Push 元素
    heap.Push(h, 6)
    fmt.Println(*h) // [1 2 3 6 4 5 7 9 8 6]

    for h.Len() != 0 {
        fmt.Printf("%d ", heap.Pop(h).(int)) // 1 2 3 4 5 6 6 7 8 9
    }
}