上一讲中我们把最大堆的基本存储和两个经典的操作进行了介绍, 并且在文章的最后, 我们依次执行了删除根节点的操作, 这时候你看到了一个排好序的数列, 本节课我就把堆排序给您讲清楚.
下面的图片是 ShiftUp 和 ShiftDown 的源码, 一是你可以验证一下自己编写的是不是合理, 再一个也是作为我们后面文字的辅助理解材料.
ShifUp 和 ShiftDown 源码
基础堆排序
基础堆排序的源码如下:
基础堆排序源码
从源码中可以看出来, 基础堆排序的过程非常简单: 先定义一个最大堆, 然后将待排序数组中的元素向最大堆中依次插入(构造最大堆的过程), 最后再把最大堆中的元素一个一个取出来(每次操作都是取出根节点), 从后向前依次放回待排序数组中.
下面是 insertItem(插入操作)和 extractItem(删除根节点操作)的源码:
insertItem 和 extractItem 的源码
基础堆排序有两个问题:
一是: 构建最大堆的过程比较繁琐, 要对每一个插入最大堆的元素进行 shiftUp 操作;
二是: 使用了额外的存储空间, 构建的最大对对象就是额外的存储空间.
下面我们先解决第一个问题.
最大堆的 heapify
heapify 操作的定义如下:
我们可以把任何一个数列看成是一个带重组的最大堆, 而这个数列中所有的叶子节点其实单独拿出来都是一个最大堆. 那我们就从最后一个非叶子开始依次往前, 对每一个非叶子节点做 shiftDown 操作, 操作完成之后, 这个数列也就变成了一个最大堆.
源码如下图所示:
heapify 源码
结合 heapify 操作, 我们可以重写堆排序的源码, 源码如下:
结合 heapify 操作的堆排序
怎么样, 看来上面两个排序的源码有什么感想呢? 我在学习这部分算法时就有一种感觉:
过程只要想清楚, 源码写出来那是即精悍, 又短小.
优化的堆排序
下面我们解决基础堆排序中的第二个问题, 即处理掉那额外的存储空间. 算法过程如下:
对于一个待排序的数组, 我们第一步要做的就是把这个数组通过 heapify 的过程先整理成最大堆. 然后, 在这个数组中, 对最大堆进行整理, 形成一个排好序的数列, 如何整理呢? 详细过程如下:
最大堆的排序过程
最大堆优化后排序的源码如下:
优化后的堆排序源码
怎么样, 是不是还是那个感觉: 即短小, 又精悍.
好, 到此为止我们已经把最基本的四种排序 (插入排序, 归并排序, 快速排序, 堆排序) 都进行了介绍, 下一篇文章我会把所有已经讲过的排序做一个总结, 希望能够对你理解排序算法有帮助.
来源: http://www.jianshu.com/p/6559464c528d