上一讲中我们把最大堆的基本存储和两个经典的操作进行了介绍，并且在文章的最后，我们依次执行了删除根节点的操作，这时候你看到了一个排好序的数列，本节课我就把堆排序给您讲清楚。

下面的图片是ShiftUp和ShiftDown的源码，一是你可以验证一下自己编写的是不是合理，再一个也是作为我们后面文字的辅助理解材料。

ShifUp和ShiftDown源码

基础堆排序

基础堆排序的源码如下：

基础堆排序源码

从源码中可以看出来，基础堆排序的过程非常简单：先定义一个最大堆，然后将待排序数组中的元素向最大堆中依次插入（构造最大堆的过程），最后再把最大堆中的元素一个一个取出来（每次操作都是取出根节点），从后向前依次放回待排序数组中。

下面是insertItem（插入操作）和extractItem（删除根节点操作）的源码：

insertItem和extractItem的源码

基础堆排序有两个问题：

一是：构建最大堆的过程比较繁琐，要对每一个插入最大堆的元素进行shiftUp操作；

二是：使用了额外的存储空间，构建的最大对对象就是额外的存储空间。

下面我们先解决第一个问题。

最大堆的heapify

heapify操作的定义如下：

我们可以把任何一个数列看成是一个带重组的最大堆，而这个数列中所有的叶子节点其实单独拿出来都是一个最大堆。那我们就从最后一个非叶子开始依次往前，对每一个非叶子节点做shiftDown操作，操作完成之后，这个数列也就变成了一个最大堆。

源码如下图所示：

heapify源码

结合heapify操作，我们可以重写堆排序的源码，源码如下：

结合heapify操作的堆排序

怎么样，看来上面两个排序的源码有什么感想呢？我在学习这部分算法时就有一种感觉：

过程只要想清楚，源码写出来那是即精悍，又短小。

优化的堆排序

下面我们解决基础堆排序中的第二个问题，即处理掉那额外的存储空间。算法过程如下：

对于一个待排序的数组，我们第一步要做的就是把这个数组通过heapify的过程先整理成最大堆。然后，在这个数组中，对最大堆进行整理，形成一个排好序的数列，如何整理呢？详细过程如下：

最大堆的排序过程

最大堆优化后排序的源码如下：

优化后的堆排序源码

怎么样，是不是还是那个感觉：即短小，又精悍。

好，到此为止我们已经把最基本的四种排序（插入排序、归并排序、快速排序、堆排序）都进行了介绍，下一篇文章我会把所有已经讲过的排序做一个总结，希望能够对你理解排序算法有帮助。

我是徐建航，这是我写的第63篇文章，欢迎你加入007社群，七天写一篇，一起写七年，七年之后一起去南极。