【排序算法】-6.堆排序

  补充概念：若设二叉树的深度为k，除第k层外，其他各层（1～（k-1）层）的节点数都达到最大值，且第k层所有的节点都连续集中在最左边，这样的树就是完全二叉树。如下图：

堆排序参见链接博客

https://www.jianshu.com/p/0d383d294a80

时间复杂度：

它是建立在初始构建堆和在重建堆时的反复筛选上，在构建堆的过程中，因为我们是完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和有必要的互换，对于每个非终端结点来说，其实最多的是进行两次比较和呼唤操作，因此整个构建堆的时间复杂度是O（n）;

正式排序的时候，第i次取堆顶记录重建堆需要用O（logi）的时间（完全二叉树的某个结点到根节点的距离为|log2i|+1）,并且需要取n-1次堆顶记录，因此，重建堆的时间复杂度为O（nlogn）

所以总体来说，堆排序的时间复杂度是O（nlogn）。由于堆排序对原始记录的排序并不敏感，因此他无论是最好、最坏、和平均时间复杂度均为O（nlogn）这在性能上远远超过冒泡、简单选择、直接插入的O（n2）的时间复杂度了。

空间复杂度：只有一个用来交换的暂存单元，也非常不错，不过由于记录的比较和交换是跳跃式的进行，因此堆排序也是一种不稳定的排序方法。

另外，由于初始构建堆所需的比较次数较多，因此，并不适合待排序列个数较少的情况。