算法-堆排序

在学习堆排序之前，我建议先从 选择排序 练手（主要是要理解选择排序的优化-竞标赛排序），可以理解为堆排序是竞标赛排序的一个演变。

思路

堆的定义按书上来会比较抽象，我理解的就是一棵二叉树上，根节点的值小于左右节点的值，并且对左右子树同样生效，那么这棵树就是一个小根堆，由此知道，根节点的值肯定是最小的。大根堆刚好就相反了。

所以堆排序就是使一棵普通二叉树变成一个最小堆取最小值并不断调整，使得原数组最终有序的过程。

排序过程有这么几步，

1. 以原数组建立一棵完全二叉树（其实就可以用原数组来表示），然后从最后一个非叶子节点开始进行堆调整（我们以大根堆为例）。关于最后一个非叶子节点的位置计算也是有公式的，不过倘若没记住，也可以倒着遍历来找。
2. 一次堆调整过程就是从指定节点开始，分别找出与其左右孩子的最大值，如果父节点已经最大，那就不用调整，如果左节点与父节点交换，则需要继续沿着左节点继续调整，如果右节点与父节点交换，则需要沿着右节点继续调整。直到遍历到边界为止。
3. 首次建立堆的话，需要对所有非叶子节点进行调整。
4. 接下去的调整只需要从堆顶（根节点）开始调整一次就可以了，因为每调整好一次，我们就会将堆顶最大值取出用来和数组末尾值进行交换，这样大值依次从数组末尾开始有序排列。而堆顶因为交换来了新值，破坏了原有堆，所以要进行调整。
5. 重复执行步骤 4 就可完成原数组的有序排列了。

相比锦标赛排序，还是有相似的地方的。

代码

代码实现的关键是首次的堆建立以及后面的堆调整，剩下的就是循环过程。起初我用的是递归实现调整，后来参考其他的实现，改写了一个循环调整过程。

github 地址：Sorting 类下面的 heapSort 以及 adjustHeap 和 adjustHeap_withLoop 方法