排序算法（九）：桶排序

2018-08-28 本文已影响9人 zhipingChen

桶排序是将待排序集合中处于同一个值域的元素存入同一个桶中，也就是根据元素值特性将集合拆分为多个区域，则拆分后形成的多个桶，从值域上看是处于有序状态的。对每个桶中元素进行排序，则所有桶中元素构成的集合是已排序的。

快速排序是将集合拆分为两个值域，这里称为两个桶，再分别对两个桶进行排序，最终完成排序。桶排序则是将集合拆分为多个桶，对每个桶进行排序，则完成排序过程。两者不同之处在于，快排是在集合本身上进行排序，属于原地排序方式，且对每个桶的排序方式也是快排。桶排序则是提供了额外的操作空间，在额外空间上对桶进行排序，避免了构成桶过程的元素比较和交换操作，同时可以自主选择恰当的排序算法对桶进行排序。

当然桶排序更是对计数排序的改进，计数排序申请的额外空间跨度从最小元素值到最大元素值，若待排序集合中元素不是依次递增的，则必然有空间浪费情况。桶排序则是弱化了这种浪费情况，将最小值到最大值之间的每一个位置申请空间，更新为最小值到最大值之间每一个固定区域申请空间，尽量减少了元素值大小不连续情况下的空间浪费情况。

桶排序过程中存在两个关键环节：

元素值域的划分，也就是元素到桶的映射规则。映射规则需要根据待排序集合的元素分布特性进行选择，若规则设计的过于模糊、宽泛，则可能导致待排序集合中所有元素全部映射到一个桶上，则桶排序向比较性质排序算法演变。若映射规则设计的过于具体、严苛，则可能导致待排序集合中每一个元素值映射到一个桶上，则桶排序向计数排序方式演化。
排序算法的选择，从待排序集合中元素映射到各个桶上的过程，并不存在元素的比较和交换操作，在对各个桶中元素进行排序时，可以自主选择合适的排序算法，桶排序算法的复杂度和稳定性，都根据选择的排序算法不同而不同。

算法过程

根据待排序集合中最大元素和最小元素的差值范围和映射规则，确定申请的桶个数；
遍历待排序集合，将每一个元素移动到对应的桶中；
对每一个桶中元素进行排序，并移动到已排序集合中。

步骤 3 中提到的已排序集合，和步骤 1、2 中的待排序集合是同一个集合。与计数排序不同，桶排序的步骤 2 完成之后，所有元素都处于桶中，并且对桶中元素排序后，移动元素过程中不再依赖原始集合，所以可以将桶中元素移动回原始集合即可。

演示示例

待排序集合为：[-7, 51, 3, 121, -3, 32, 21, 43, 4, 25, 56, 77, 16, 22, 87, 56, -10, 68, 99, 70]
映射规则为： $f(x)=\frac x{10}-c$ ，其中常量位： $c=\frac {min}{10}$ ，即以间隔大小 10 来区分不同值域
排序算法为：堆排序，根据堆排序特性可知， $K$ 个元素的集合，时间复杂度为： $Klog_2K$ ，算法不保持稳定性

step 1:

遍历集合可得，最大值为： $max=121$ ，最小值为： $min=-10$ ，待申请桶的个数为： $\frac {max}{10}-\frac {min}{10}+1=12-(-1)+1=14$

step 2:

遍历待排序集合，依次添加各元素到对应的桶中。

桶下标	桶中元素
0	-7, -3, -10
1	3, 4
2	16
3	21, 25, 22
4	32
5	43
6	51, 56, 56
7	68
8	77, 70
9	87
10	99
11
12
13	121

step 3:

对每一个桶中元素进行排序，并移动回原始集合中，即完成排序过程。

算法示例

def bucketSort(arr):
    maximum, minimum = max(arr), min(arr)
    bucketArr = [[] for i in range(maximum // 10 - minimum // 10 + 1)]  # set the map rule and apply for space
    for i in arr:  # map every element in array to the corresponding bucket
        index = i // 10 - minimum // 10
        bucketArr[index].append(i)
    arr.clear()
    for i in bucketArr:
        heapSort(i)   # sort the elements in every bucket
        arr.extend(i)  # move the sorted elements in bucket to array

第一个循环作用为将待排序集合中元素移动到对应的桶中，复杂度为 $O(N)$ ；第二个循环的作用为对每个桶中元素进行排序，并移动回初始集合中，若桶个数为 $M$ ，平均每个桶中元素个数为 $\frac NM$ ，则复杂度为 $O(M*\frac NMlog_2{\frac NM}+N)=O(N+N(log_2N-log_2M))$ 。当 $M==N$ 时，即桶排序向计数排序方式演化，则堆排序不发挥作用，复杂度为 $O(N)$ ，只需要将元素移动回初始集合即可。当 $M==1$ 时，即桶排序向比较性质排序算法演化，对集合进行堆排序，并将元素移动回初始集合，复杂度为 $O(N+Nlog_2N)$ 。

算法分析

由算法过程可知，桶排序的时间复杂度为 $O(N+N(log_2N-log_2M))$ ，其中 $M$ 表示桶的个数。由于需要申请额外的空间来保存元素，并申请额外的数组来存储每个桶，所以空间复杂度为 $O(N+M)$ 。算法的稳定性取决于对桶中元素排序时选择的排序算法。由桶排序的过程可知，当待排序集合中存在元素值相差较大时，对映射规则的选择是一个挑战，可能导致元素集中分布在某一个桶中或者绝大多数桶是空桶的现象，对算法的时间复杂度或空间复杂度有较大影响，所以同计数排序一样，桶排序适用于元素值分布较为集中的序列。