《恋上数据结构与算法》排序（三）：堆排序

堆排序（Heap Sort）

请先看看什么是堆, 以及如何实现二叉堆 : 《恋上数据结构与算法》笔记（十七）：二叉堆

一、概念

• 堆排序可以认为是对选择排序算法中寻找最小（大）元素的优化。
• 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
• 一般升序采用大顶堆，降序采用小顶堆。

堆排序步骤 :

1. 交换堆顶与尾元素。
2. 堆的元素数量减1。
3. 对0位置进行siftDown操作。
4. 重复执行1-3操作，直到堆的元素数量为1。