桶排序(Bucket Sort)算法是先将大量数据分类成少量数据后,再进行排序的算法。可以透过简单的表达式来完成数据的分类,在最好的情况之下,数据可以被完全打散,此时的时间复杂度就会是一个线性时间。

桶排序法(Bucket Sort)

桶排序法的概念

桶排序法会将数据先分类丢进不同的桶子中,接着再将所有桶子以插入排序等适合少量数据的算法进行排序之后,再依照桶子的顺序把桶子中的元素串接在一起,如此一来就能完成所有排序。在一开始的分类数据的时候,也要注意到桶子的顺序,譬如要将一个整数串行进行递增排序,我们可以把值比较小的整数群丢进第一个桶子中;把值比较大的整数群丢进第二个桶子中。

桶排序法的过程

假设现在有个数组数据,内容如下:

索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79

现在有九个桶子,用来分别保存 0~9、10~19、20~29、30~39、40~49、50~59、60~69、70~79、80~89 的整数数据。

桶子号码    0   1   2   3   4   5   6   7   8
桶子内容   []  []  []  []  []  []  []  []  []

要如何将数组递增排列呢?

我们可以走访数组中的所有元素,元素值除 10 的整数部份即为其要被丢进去的桶子号码。例如 79 这个元素,就会被丢进 7 这个号码的桶子里。所以在所有元素都依走访顺序被丢进桶子之后,桶子此时保存的数据如下表:

桶子号码        0             1             2             3             4             5             6             7             8
桶子内容   [9, 2]            []            []  [30, 38, 32]          [47]            []      [69, 61]          [79]          [81]

接着分别将这些桶子进行排序,排序后的结果如下:

桶子号码        0             1             2             3             4             5             6             7             8
桶子内容   [2, 9]            []            []  [30, 32, 38]          [47]            []      [61, 69]          [79]          [81]

最后再依照桶子的顺序,把桶子中的元素合并成串行,就会是已排序好的串行了!

桶排序法的程序实作

这边的程序实作是以非常通用的方式来完成,先把数据的最小值、最大值,和每个桶子可保存的元素数量先设置好,接着再算出最大需要的桶子个数,有了这些信息之后再把桶子创建出来,元素可以依照其值落在哪个数值范围,来被决定丢进哪个桶子。在实务上,为了使数据尽可能分散到不同的桶子中,实作起来并不会这么地单纯。

桶排序法的复杂度

桶排序法的复杂度主要还是得看其使用到的数据结构,如果是单纯地类似以上实作的方式来完成,在此以 #{{n}}# 来表示要排序的数据笔数,以 #{{k}}# 来表示要排序的数据可能的值的数量,以 #{{m}}# 来表示桶子的数量。

项目 值 备注
最差时间复杂度 #{{O(n^2)}}# 元素都在同一个桶子中,而且使用的排序算法也遭遇最差状况。
最佳时间复杂度 #{{O(n + m)}}# 元素完全分散在不同的桶子中,完全不需进行排序。
平均时间复杂度 #{{O(n + {{n^2} \over m} + m )}}#
最差空间复杂度 #{{O(n + k)}}#
#{{O(n \times k)}}#
?
不预先配置桶子的空间。
预先配置桶子的空间。
使用了其它需要额外空间的排序算法。
是否稳定 是
否
使用稳定排序法来排序每个桶子。
有使用到不稳定排序法。