图解堆排序（三）完整的堆排序

图解堆排序（一）什么是堆和堆的性质

图解堆排序（二）堆的基本操作

这是我们介绍堆排序的最后一篇文章，只要理解了前两篇文章的内容，那么这篇文章的内容也很好理解。尤其是第二篇文章，它讲述了如何构造一个大顶堆以及如何进行大顶堆调整。

1. 堆排序

在第一篇文章中我们已经概述了堆排序的主要思想，这里我们用一个详细的示例来展示堆排序的完整过程。

我们先对用于展示堆排序的图片元素进行说明，图1~图5中的蓝色表示还未排好序的元素，绿色表示已排好序的元素；红色表示不满足大顶堆要求的结点，即它小于它的某个孩子节点，需要对它进行大顶堆调整。

为了展示的连贯，图1~图5中后一幅图的第一个堆和序列就是上一幅图的最后一个堆和序列；图3~图5包含两行内容（用虚线分隔），后一行开始的堆和序列其实也就是前一行结束的堆和序列。

假设我们需要对一个具有n个元素的序列进行升序（从小到大）排序，那么堆排序的步骤如下所示：

1. 将原序列构造成一个大顶堆，如图1所示。图中原序列为[77, 96, 83, 52, 29]，共有5个元素，即该例中n=5。

图1 将原序列构造成大顶堆

2. 将该大顶堆的根结点（它在序列中的下标为0）和序列中的最后一个元素（它也是该大顶堆的最后一个结点）交换位置。此时，这个序列中最大的元素就在序列中最后的位置上了，而大顶堆除根结点外的所有剩余结点都在序列的前n-1个位置上。图2展示了这一过程。

图2 排好序列中最大的元素

3. 然后对序列中前n-1个位置上的结点进行大顶堆调整，使这些结点重新形成一个大顶堆。然后将该大顶堆的根结点和序列中倒数第二个元素交换位置。此时，这个序列中第二大的元素就在序列中倒数第二的位置上了，而大顶堆的剩余结点在序列的前n-2个位置上。图3展示了这一过程。

图3 排好序列中第二大的元素

4. 继续对序列中前n-2个位置上的结点进行大顶堆调整，使这些结点重新形成一个大顶堆。然后将该大顶堆的根结点和序列中倒数第三个元素交换位置。此时，这个序列中第三大的元素就在序列中倒数第三的位置上了，而大顶堆的剩余结点在序列的前n-3个位置上。图4展示了这一过程。

图4 排好序列中第三大的元素

5. 重复这一过程，最终必然形成一个有序的序列；图5展示了该示例最终的排序结果。

图5 重复堆调整和交换过程，直到整个序列排好序

我们需要知道的是具有n个元素的序列只需要n-1趟，因为每一趟都将未排序的元素中最大的那个放到它最终的位置上，因此前n-2趟已经将最大的那n-2个元素排好序了。第n-1趟开始时，还有两个元素（它们处于序列的前两个位置上）没有排好序。该趟正是在这两个元素中选出较大的那个，并将它交换到它最终的位置上，同时最小的那个元素也被交换到了最开始的位置上。因此，不再需要第n趟排序了。

2. 堆排序的不稳定性

我们之前提到过堆排序是不稳定的排序算法，在理解了堆排序的完整过程后，通过一个简单的例子就能明白它为什么是不稳定的。

图6 堆排序的不稳定性

在图6中的待排序序列为[77a, 45, 77b]，其中第一个和第三个元素的值都为77，它们是相等的，而后缀a和b只是用于区分这两个数值77。排序前，77a在77b之前。构造成大顶堆之后（其实该序列本身就已是大顶堆），77a是该大顶堆的根结点，所以在第一趟排序中它被交换到序列的最后一个位置上。因此，整个序列排好序后，77b必定在77a之前。即待排序序列中两个相等的元素的相对前后位置，在进行堆排序后可能改变，因此堆排序是不稳定的。

3. 代码实现

我们依旧用C语言来实现最终的堆排序算法的代码，这需要引用我们在第二篇文章中实现的构造大顶堆和调整大顶堆的算法。

4. 复杂度分析

堆排序主要的开销有两部分：最初构造大顶堆和后面反复的堆调整。其实这两个过程都涉及堆调整，因此我们先来看一次堆调整的开销。

堆调整的开销主要由循环语句造成（你可能需要回顾一下第二篇文章中介绍的堆调整的过程），每次循环都将待调整结点向下移动一层，最多移到叶子层。而每次循环的主要操作是两次比较，一次是在两个孩子结点之间以找到较大的那个，另一次是在父结点和较大孩子结点之间。因此，对于一个深度为d的完全二叉树（它代表一个需要调整的堆），对它进行堆调整时最多进行2(d-1)次比较。

现在，我们就来分析构造一个堆的开销。一个深度为d的完全二叉树，它的第k层最多有2^(k-1)个结点，并且以这一层的结点为根的子树的深度为d-k+1。构造堆需要从最后一个内部结点（它在倒数第二层，即d-1层）开始直到根结点，因此构造堆的过程中，总的比较次数不超过公式①。

图7 公式①~⑦

对于有n个结点的完全二叉树，它的深度d和n之间的关系为公式②；根据公式②可以推出公式③，进而推出公式④；将公式④代入公式①的最右边部分，可以推出公式⑤。对通项为 j/(2^j) 的数列进行求和（这是高中的知识）可以得到公式⑥；将公式⑥代入公式⑤，可以得到公式⑦；而公式⑦的左边部分其实就是公式①的最右边部分。因此当序列有n个元素时，将它构造成堆的总比较次数小于4n，即构造堆的时间复杂度为O(n)。

再来分析后面进行反复堆调整时的开销。我们在第1小节的最后说过，堆排序一共要进行n-1趟，但第1趟其实利用的是最初构造的堆，因此后面的n-2趟才需要每次都进行堆调整。第 i 趟（i的取值范围为[2, n-1]）要调整的完全二叉树有n-i+1个结点，因此这n-2趟堆调整涉及的完全二叉树的结点数组成的序列是[n-1, n-2, ···, 2]。

根据公式②可以计算出每一趟要调整的完全二叉树的深度，假设为h，那么该趟需要的比较次数就是2(h-1)。因此总共需要的比较次数为公式⑧的左边部分。我们显然可知公式⑧中左边的每一项都小于公式⑨，并且公式⑧左边的总项数也小于n，因此我们可以得到公式⑧。因此，反复进行堆调整的时间复杂度为O(n·logn)。

图8 公式⑧~⑨

将上面两种情况综合起来，可得堆排序的时间复杂度为O(n·logn)，这是一个相当高效的时间复杂度，也说明了堆排序的性能非常好。

最后再来分析它的空间复杂度，这就比较简单了，堆排序过程中只需几个额外变量用来交换元素以及作为循环控制变量。它们的数量固定且和原序列的长度无关，因此堆排序的空间复杂度为O(1)。

（完）