三十天挑战数据结构（14）堆排序——十分钟带你透彻领悟

数据结构第九章内部排序简单的非常简单易懂好理解，难的非常？？绕（起码对于一个初学者我觉得有点算法光看书来并不太好理解），堆排序就是其中一个。
堆排序我自己看了很多参考资料搜了很多博客，看代码也觉得乱乱的，一直拖着没有来解决它，直到今早上临近ddl迫不得已要把书上习题搞定，再看了几遍，在前几次的积淀下这次居然莫名其妙地就明白了。
总之它的思路在你明白了之后还是很清晰简单的，所以我觉得它值得单独用一篇文章来好好讲讲，让自己也透彻地领悟！

首先我们大致要明白是基于“树”的操作（大部分我觉得都是二叉树），那么就需要两个新鲜的概念：大顶堆和小顶堆。

大顶堆：每一个根节点的值都比左右子树的结点值大，例如：

小顶堆：每一个根节点的值都比左右子树的结点值小，例如：

要使用堆排序来进行一个无序序列的排序，简言之就是不断将树转换成大顶堆 -> 顶端结点和末尾结点交换位置的循环过程。
这样听起来是不是还蛮简单的？许多教辅书上往往仔细阐述了转化大顶堆过程然后便很简略的说了交换便结束了，很少有教材能够给出一个完整的堆排序过程。但我在学习这个算法的时候自认为还是很有必要看一下全过程的，不然你并无法清楚地看出整个排序过程是怎么完成的。

好的那让我们一起举一个6个元素的简单例子，并用图来形象地理解堆排序过程：
待排序序列：39、24、18、30、04、66
首先我们按照层序建立的方法来建立这棵二叉树（这个纸上很好画出来，代码的话可能有点冗杂可以看我之前的一篇博客：三十天挑战数据结构（2）层序建立二叉树、先序输出），建立好的二叉树长这样：

现在这棵树很没有规律，我们需要把它变成一个大顶堆。将一颗二叉树变成大顶堆的直接方法就是按照先序遍历（或者层序，都可以），检查每一个孩子结点是不是都大于它的根节点，如果是，就检查下一个结点，如果不是，则和它左右孩子中最大的那个交换。
依次进行下去直到这棵二叉树变成大顶堆，这里我们用第一步调整大顶堆为例，详细画一下每一步过程：



这里注意，在交换了18和66之后，39和66成为了父子关系，但是不满足39 > 66，因此还需要做一次调整：

好现在纵观一下，会发现已经成为一个大顶堆了。调整大顶堆的过程还是挺机械的是吧？只是不断地去判断，但凡遇到了一个结点小于某子结点的就交换一下。

有了一个大顶堆，我们的堆排序就完成一半了！（bushi）但至少我们重复的过程的一大半都完成了，接下来需要做的就只是，将堆顶结点和最下方的结点交换一下位置，甭管它是多少，交换就完事。
有人可能会问，为什么要这样交换呢？你想啊你现在这是一个大顶堆，子结点大小我们说不清楚，但根结点一定是所有数据中最大的对不对！换句话说我们一次调整的过程，其实就是将现序列中最大的数挪到最后。

所以现在就是这样的情况了：


好现在我们可以忽略绿色的结点了，看剩下的这个二叉树，是不是觉得又变得杂乱无章了起来？是的是的没关系，我们需要做的只是重新按照刚刚的步骤来一次~

首先是第二次调整成大顶堆：

交换：注意这里交换的是肉眼看出来的末尾，不要想那么多遍历顺序，一定要说的话就是除去绿色结点层序的末尾


再进行第三次大顶堆调整：

交换：


第四次调整大顶堆：

交换：

第五次调整大顶堆：

交换：

至此，所有的排序已经结束：


是不是一步一步看就发现挺清晰的？这种题最直观的做法就是画图了，想尝试的话可以自己找一些序列来进行排序，还是很有趣der！

堆排序的大致算法思路就是这样，代码就不搞了先，可以参照其他许多优秀博主的代码，记住学算法最重要的就是理解，然后才是去学习实现！