堆积排序(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)}}#
是否稳定 否