排序算法——堆排序

前言

理一下堆排序的实现原理，以最大堆为例。

原理

实际以数组 Array 来存储，构建完全二叉树。最后一个有子节点的节点的数组下标为 Array.count / 2 - 1.以最大堆为例，从最后一个有子节点的节点 Node 开始一直到根结点，将 Node 与其较大的子节点交换，交换后如果还比子节点小，继续与子节点交换。最后构成最大堆。然后将最后一个节点与根结点交换，弹出根节点。

例子

3，44，38，5，47，15

按顺序构建堆为

最后一个有子节点的节点的数组下标为 6 / 2 - 1 = 2，也就是 38

排序过程：

1.
38。大于 15，不用管

2.
44。 与较大的子节点 47 交换

3.
3。 与较大的 47 交换，然后再与 44 交换，构成最大堆。

4.
将最后一个节点 15 与根结点 47 交换，弹出 47

5.
将剩下的依次构建最大堆，直到结束。