堆排序基本信息

堆排序是基于比较的二进制堆数据结构排序技术。它类似于选择排序,我们首先找到最大元素并将其放在数据结构的末尾。然后对剩余的项目重复相同的过程。

堆排序的伪代码:

function heapsort(input, count)
    heapify(a,count)
    end <- count - 1
    while end -> 0 do
    swap(a[end],a[0])
    end<-end-1
    restore(a, 0, end)

function heapify(a, count)
    start <- parent(count - 1)
    while start >= 0 do
        restore(a, start, count - 1)
        start <- start - 1

堆排序示例:

StackOverflow 文档

辅助空间: O(1)
时间复杂度: O(nlogn)