堆排序及优化

关于堆的内容请看我这篇文章的实现
https://www.jianshu.com/p/1e3a94f6c681

下面我们说说堆排序
既然我们已经有了堆，那么堆排序就显得十分容易了

func HeapSortOne(arr []int) {
    maxHeap := MaxHeap{}
    maxHeap.Init(len(arr))
    for _, e := range arr {
        maxHeap.Insert(e)
    }
    for i := range arr {
        arr[i] = maxHeap.Extract()
    }
}

上面的代码就是先生成一个堆，然后将需要排序的元素放入堆中，再从堆中取出，这样就完成了排序。这种方法虽然简单，但是存在着缺陷，就是函数内部需要一个和需要排序的序列大小一样的序列，十分消耗内存，下面我们改进一下。

func HeapSortTwo(arr []int) {
    // heapify操作，使其变成一个堆
    for i := (len(arr) - 2) / 2; i >= 0; i-- {
        shiftDown(arr, len(arr)-1, i)
    }

    // 将第一个和最后一个元素交换
    // 这样就可以认为最后一个元素找到了位置
    // 再改变第一个元素的位置，维护这个除了最后一个元素的堆
    for i := len(arr) - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        shiftDown(arr, i-1, 0)
    }
}

func shiftDown(arr []int, n int, i int) {
    temp := arr[i]
    for i*2+1 <= n {
        k := i*2 + 1
        if k+1 <= n && arr[k+1] > arr[k] {
            k++
        }
        if temp >= arr[k] {
            break
        }
        arr[i] = arr[k]
        i = k
    }
    arr[i] = temp
}