内部排序：堆排序

内部排序：堆排序2014-12-06 未知前言

堆排序、快速排序、归并排序（下篇会写这两种排序算法）的平均时间复杂度都为O（n*logn）。要弄清楚堆排序，就要先了解下二叉堆这种数据结构。本文不打算完全讲述二叉堆的所有操作，而是着重讲述堆排序中要用到的操作。比如我们建堆的时候可以采用堆的插入操作（将元素插入到适当的位置，使新的序列仍符合堆的定义）将元素一个一个地插入到堆中，但其实我们完全没必要这么做，我们有执行操作更少的方法，后面你会看到，我们基本上只用到了堆的删除操作，更具体地说，应该是删除堆的根节点后，将剩余元素继续调整为堆的操作。先来看二叉堆的定义。

二叉堆

二叉堆其实是一棵有着特殊性质的完全二叉树，这里的特殊性质是指：

1、二叉堆的父节点的值总是大于等于（或小于等于）其左右孩子的值；

2、每个节点的左右子树都是一棵这样的二叉堆。

如果一个二叉堆的父节点的值总是大于其左右孩子的值，那么该二叉堆为最大堆，反之为最小堆。我们在排序时，如果要排序后的顺序为从小到大，则需选择最大堆，反之，选择最小堆，这点通过后面对堆排序分析，你会有所体会。

堆排序

由二叉堆的定义可知，堆顶元素（即二叉堆的根节点）一定为堆中的最大值或最小值，因此如果我们输出堆顶元素后，将剩余的元素再调整为二叉堆，继而再次输出堆顶元素，再将剩余的元素调整为二叉堆，反复执行该过程，这样便可输出一个有序序列，这个过程我们就叫做堆排序。

由于我们的输入是一个无序序列，因此要实现堆排序，我们要先后解决如下两个问题：

1、如何将一个无序序列建成一个二叉堆；

2、在去掉堆顶元素后，如何将剩余的元素调整为一个二叉堆。

针对第一个问题，可能很明显会想到用堆的插入操作，一个一个地插入元素，每次插入后调整元素的位置，使新的序列依然为二叉堆。这种操作一般是自底向上的调整操作，即先将待插入元素放在二叉堆后面，而后逐渐向上将其与父节点比较，进而调整位置。但正如前言中所说，我们完全用不着一个节点一个节点地插入，那我们要怎么做呢？我们需要先来解决第二个问题，解决了第二个问题，第一个问题问题也就迎刃而解了。

调整二叉堆

要分析第二个问题，我们先给出以下前提：

1、我们排序的目标是从小到大，因此我们用最大堆；

2、我们将二叉堆中的元素以层序遍历后的顺序保存在一维数组中，根节点在数组中的位置序号为0。

这样，如果某个节点在数组中的位置序号为i，那么它的左右孩子的位置序号分别为2i+1和2i+2。

为了使调整过程更易于理解，我们采用如下二叉堆来分析（注意下面的分析，我们并没有采用额外的数组来存储每次去掉的堆顶数据）：

这里数组A中元素的个数为8，很明显最大值为A0，为了实现排序后的元素按照从小到大的顺序排列，我们可以将二叉堆中的最后一个元素A7与A0互换，这样A7中保存的就是数组中的最大值，而此时该二叉树变为了如下情况：