堆积排序(Heap Sort)算法是利用完全二元树(Complete Binary Tree),也就是堆积(Heap)结构来完成排序的算法。虽然说要用到堆积结构,看起来好像很复杂似的,但其实这个只要一般的数组结构(可以直接用要排序的数组来制作)就能实作出来,而且实作出来的速度保证不会太慢,再怎么差都会有 O(nlogn) 的时间复杂度。
堆积排序法(Heap Sort)
堆积排序法的概念
堆积排序法有两个大步骤,第一个是把要排序的数组制作成「最小堆积」(Min Heap)或是「最大堆积」(Max Heap)。如果要将数组递增排序的话就使用最大堆积;如果要递减排序的话就使用最小堆积。接下来的步骤就是利用最大堆积和最小堆积来进行排序,方法和创建最大堆积或是最小堆积时是几乎一样的。
什么是完全二元树?完全二元树是一种二元树,它只允许最后一层(最底下那层)的节点数量可以不必填满(若顶层是第 1 层,则第 n 层的最大节点数量为 2n-1),而且最后一层的节点必须由左至右连续排列,中间不能有空缺。例如以下结构即为完全二元树:
5 / \ 1 3 / \ / 6 2 4
什么是最小堆积?最小堆积就是上层节点数值必定会小于下层节点数值的完全二元树。例如以下结构即为最小堆积:
1 / \ 2 3 / \ / 4 6 5
什么是最大堆积?最大堆积就是上层节点数值必定会大于下层节点数值的完全二元树。例如以下结构即为最大堆积:
6 / \ 5 3 / \ / 4 2 1
数组可以依照索引顺序,由左至右、由上到下表示出一个完全二元树。例如以上的最大堆积,可以是以下这个数组:
索引 0 1 2 3 4 5 数值 6 5 3 4 2 1
堆积排序法的过程
假设现在有个数组数据,内容如下:
索引 0 1 2 3 4 5 6 7 8 9 数值 69 81 30 38 9 2 47 61 32 79
要如何将它递增排列呢?
我们先将这个数组用完全二元树的结构来表示,如下:
69
/ \
/ \
/ \
81 30
/ \ / \
/ \ / \
38 9 2 47
/ \ /
61 32 79
由于我们要进行递增,因此要先将这个完全二元树变成最大堆积。于是我们从最下面的两层开始,把比上层大的元素交换到上层。
首先看到 47,由于它没有子节点,因此还不用交换。
69
/ \
/ \
/ \
81 30
/ \ / \
/ \ / \
38 9 2 47*
/ \ /
61 32 79
2,也没有子节点,因此不用交换。
69
/ \
/ \
/ \
81 30
/ \ / \
/ \ / \
38 9 2* 47
/ \ /
61 32 79
再来看到 9,9 有一个值为 79 的子节点。由于 79 比 9 大,所以要交换上来。
69
/ \
/ \
/ \
81 30
/ \ / \
/ \ / \
38 9* 2 47
/ \ /
61 32 79↑
69
/ \
/ \
/ \
81 30
/ \ / \
/ \ / \
38 79+ 2 47
/ \ /
61 32 9*
此时 9 已没有子节点了,结束交换。
再来看到 38,38 有两个子节点,最大的子节点为 61。由于 61 比 38 大,所以要交换上来。
69
/ \
/ \
/ \
81 30
/ \ / \
/ \ / \
38* 79 2 47
/ \ /
61↑32 9
69
/ \
/ \
/ \
81 30
/ \ / \
/ \ / \
61+ 79 2 47
/ \ /
38* 32 9
此时 38 已没有子节点了,结束交换。
依此类推,剩下的最大堆积的建构过程如下:
69
/ \
/ \
/ \
81 30*
/ \ / \
/ \ / \
61 79 2 47↑
/ \ /
38 32 9
69
/ \
/ \
/ \
81 47+
/ \ / \
/ \ / \
61 79 2 30*
/ \ /
38 32 9
69
/ \
/ \
/ \
81* 47
/ \ / \
/ \ / \
61 79 2 30
/ \ /
38 32 9
69*
/ \
/ \
/ \
81↑ 47
/ \ / \
/ \ / \
61 79 2 30
/ \ /
38 32 9
81+
/ \
/ \
/ \
69* 47
/ \ / \
/ \ / \
61 79↑ 2 30
/ \ /
38 32 9
81+
/ \
/ \
/ \
79 47
/ \ / \
/ \ / \
61 69* 2 30
/ \ /
38 32 9
81
/ \
/ \
/ \
79 47
/ \ / \
/ \ / \
61 69 2 30
/ \ /
38 32 9
至此,最大堆积就创建好了!
接下来的工作就是排序啦!由于我们现在已经知道这个结构中的最大值是最顶层的节点,且我们要把数组做递增排列。所以我们可以直接把顶层的节点,也就是最大值与数组的最后一个元素做交换,如此一来我们的递增排序就已经排好一个元素了。
9*
/ \
/ \
/ \
79↑ 47
/ \ / \
/ \ / \
61 69 2 30
/ \ /
38 32 81-
但别忘了要继续维持住我们的最大堆积条件,所以还是得做交换才行。由于此时 81 已经在数组的正确位置上,我们可以直接把它从最大堆积的考虑范围中排除,不要再去动它了。
79+
/ \
/ \
/ \
9* 47
/ \ / \
/ \ / \
61 69↑ 2 30
/ \ /
38 32 81-
79+
/ \
/ \
/ \
69 47
/ \ / \
/ \ / \
61 9* 2 30
/ \ /
38 32 81-
79
/ \
/ \
/ \
69 47
/ \ / \
/ \ / \
61 9 2 30
/ \ /
38 32 81-
接下来就是让 32 要与这个最大堆积结构中的最大值,也就是最顶层的节点做交换啦!之后的步骤都跟刚才把 81 换下来时一样,如下:
32*
/ \
/ \
/ \
69↑ 47
/ \ / \
/ \ / \
61 9 2 30
/ \ /
38 79- 81-
69+
/ \
/ \
/ \
32* 47
/ \ / \
/ \ / \
61↑ 9 2 30
/ \ /
38 79- 81-
69+
/ \
/ \
/ \
61 47
/ \ / \
/ \ / \
32* 9 2 30
/ \ /
38↑79- 81-
69+
/ \
/ \
/ \
61 47
/ \ / \
/ \ / \
38 9 2 30
/ \ /
32* 79- 81-
69
/ \
/ \
/ \
61 47
/ \ / \
/ \ / \
38 9 2 30
/ \ /
32 79- 81-
32*
/ \
/ \
/ \
61↑ 47
/ \ / \
/ \ / \
38 9 2 30
/ \ /
69- 79- 81-
61+
/ \
/ \
/ \
32* 47
/ \ / \
/ \ / \
38↑ 9 2 30
/ \ /
69- 79- 81-
61+
/ \
/ \
/ \
38 47
/ \ / \
/ \ / \
32* 9 2 30
/ \ /
69- 79- 81-
61
/ \
/ \
/ \
38 47
/ \ / \
/ \ / \
32 9 2 30
/ \ /
69- 79- 81-
30*
/ \
/ \
/ \
38 47↑
/ \ / \
/ \ / \
32 9 2 61-
/ \ /
69- 79- 81-
47+
/ \
/ \
/ \
38 30*
/ \ / \
/ \ / \
32 9 2 61-
/ \ /
69- 79- 81-
47
/ \
/ \
/ \
38 30
/ \ / \
/ \ / \
32 9 2 61-
/ \ /
69- 79- 81-
2*
/ \
/ \
/ \
38↑ 30
/ \ / \
/ \ / \
32 9 47- 61-
/ \ /
69- 79- 81-
38+
/ \
/ \
/ \
2* 30
/ \ / \
/ \ / \
32↑ 9 47- 61-
/ \ /
69- 79- 81-
38+
/ \
/ \
/ \
32 30
/ \ / \
/ \ / \
2* 9 47- 61-
/ \ /
69- 79- 81-
38
/ \
/ \
/ \
32 30
/ \ / \
/ \ / \
2 9 47- 61-
/ \ /
69- 79- 81-
9*
/ \
/ \
/ \
32↑ 30
/ \ / \
/ \ / \
2 38- 47- 61-
/ \ /
69- 79- 81-
32+
/ \
/ \
/ \
9* 30
/ \ / \
/ \ / \
2 38- 47- 61-
/ \ /
69- 79- 81-
32
/ \
/ \
/ \
9 30
/ \ / \
/ \ / \
2 38- 47- 61-
/ \ /
69- 79- 81-
2*
/ \
/ \
/ \
9 30↑
/ \ / \
/ \ / \
32- 38- 47- 61-
/ \ /
69- 79- 81-
30+
/ \
/ \
/ \
9 2*
/ \ / \
/ \ / \
32- 38- 47- 61-
/ \ /
69- 79- 81-
30
/ \
/ \
/ \
9 2
/ \ / \
/ \ / \
32- 38- 47- 61-
/ \ /
69- 79- 81-
2*
/ \
/ \
/ \
9↑ 30-
/ \ / \
/ \ / \
32- 38- 47- 61-
/ \ /
69- 79- 81-
9+
/ \
/ \
/ \
2* 30-
/ \ / \
/ \ / \
32- 38- 47- 61-
/ \ /
69- 79- 81-
9
/ \
/ \
/ \
2 30-
/ \ / \
/ \ / \
32- 38- 47- 61-
/ \ /
69- 79- 81-
2
/ \
/ \
/ \
9- 30-
/ \ / \
/ \ / \
32- 38- 47- 61-
/ \ /
69- 79- 81-
这样就完成排序啦!
堆积排序法的程序实作
>> 1 等同于「除以 2 取整数」;<< 1 等同于「乘以 2」。
堆积排序法的复杂度
以 #{{n}}# 来表示要排序的数据笔数。
| 项目 | 值 | 备注 |
|---|---|---|
| 最差时间复杂度 | #{{O(n \log n)}}# | |
| 最佳时间复杂度 | #{{O(n)}}# | 要排序的元素值都一样时。 |
| 平均时间复杂度 | #{{O(n \log n)}}# | |
| 最差空间复杂度 | #{{O(1)}}# | |
| 是否稳定 | 否 |

