Question

我看书上堆排序，每次都要重新建堆，然后再调外根节点和最后一个结点，感觉这样好麻烦？你们是怎么做的呢

Answer 1

堆排序很重要的一个步骤是初始建堆，它保证了树中的每个子树的根结点都比其下的子结点大。
建堆后的过程基本上就是选择出最大值，然后将被交换到根结点位置的结点进行下沉的过程。而这些过程虽然对树的局部结构进行了调整，但严格来说，不算是重新建堆。
《算法导论》上对堆排序讲得很详细。它把堆排序算法分成了三个子算法：
一个将结点下沉的递归算法；一个初始建堆算法和一个排序算法。
具体过程是：
1、初始建堆算法调用结点下沉递归算法完成建堆；
2、排序算法在建好的堆上得到根结点(即最大值)，然后调用结点下沉的递归算法将交换到根结点位置的结点进行下沉。反复第2步，整个算法就完成了。
思路很清晰，可以去看看。

Answer 2

堆排序就是这样的啊，每一趟将堆顶和最后一个元素互换，再调整