堆排序（heap sort）是一种树形选择排序方法。他的特点是将R[1..n] (为配合二叉树的顺序存储结构，这里我们从1开始计算下标)看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中父结点和子节点之间的位置关系在无序区中选择最大（或者最小）的元素。

堆排序的排序过程与简单选择排序类似，只是挑选最大或者最小元素时采用的方法不同，这里采用大根堆，每次挑选最大元素归位。挑选最大元素是采用筛选（sift）的方法实现的。

其最好、最坏、平均时间复杂度均为O(nlog~2~n)

只使用了i，j，tmp三个辅助变量，与问题规模n无关。空间复杂度为O(1)

相同元素的相对位置可能改变，这是一种不稳定的排序方法。

是，堆排序每趟产生的有序区一定是全局有序区。