排序算法之HeapSort
堆排序是一种基于比较的排序算法，可以简单的认为是一种改进的选择排序，虽然在实际中比快速排序要慢，但是其优势是最坏情况基本也是O(n log n)的时间复杂度，空间复杂度是O(1)，也就是不需要额外的内存空间。堆排序是稳定的排序算法。
理解堆排序首先要了解什么是堆，堆分为大根堆和小根堆，如果根节点是最小的数，为小根堆，根节点是最大的数，为大根堆，堆一般使用一维的数组来表示，可以看做是一个完全的二叉树：
- 树的根节点是array[0]
- 每个节点的左子节点为array[2i + 1]
- 每个节点的右子节点为array[2i + 2]
- 每个节点的父节点为array[floor((i - 1) / 2)]
堆排序算法可以被分成两个部分：
- 建立大(小)根堆
- 堆排序
以上两部操作都涉及到堆调整，调整的目的是建立完全最大(小)根堆。
建堆就是建立一个大根堆或者小根堆，以大根堆为例，假设有下列数组
1 | [1,4,7,6,11,5,8,2,10,9,3] |
初始堆如下图：
首先我们要建立完全最大堆，起始选取最后一个叶子节点的父节点，假设该节点为array[i]，本例i = 4，比较该节点与其子节点，如果子节点比其大，选取最大的子节点与其进行交换，该例子中11 > 9 > 3，所以不需要交换，然后比较array[i--]，同样的逻辑，这时6 > 2 < 10，所以交换6和10，变换后如下图(蓝色表示交换过位置)
之后继续比较array[i--]，那么7和8要交换位置，变化结果如下
之后继续比较array[i--]，4和11要交换位置，变化结果如下
因为4和11交换后，4作为父节点，不一定满足完全大根堆，所以要比较4和其子节点，如果子节点大的话，需要交换，那么这一步的变换如下
之后继续比较array[i--]，1和11要交换位置，变化结果如下
因为1和11交换后，1作为父节点，不一定满足完全大根堆，所以要比较1和其子节点，如果子节点大的话，需要交换，那么这一步的变换如下
之后同理，1沉到最下面
到此为止，建堆的过程就结束了。
接下来要做堆排序，过程简单描述就是堆顶元素和数组最后一个元素交换位置，交换后，对二叉树进行剪枝，排除最后一个元素，然后从堆顶开始调整堆，重复上面的过程。
变换图如下(绿色表示剪枝)
到目前位置最后两位的数据排序是正确的，后面继续该流程就完成了整个堆排序的过程，这里就不继续贴图了。
参考
堆排序-Wikipedia
heapsort-Wikipedia
Sorting_algorithm#Stability