线性时间非比较类排序之桶排序

桶排序

桶排序也叫箱排序，1956年便开始使用，它可以算是计数排序的一个改进版本。

1. 算法思想

根据元素的特性将集合拆分为多个值域，我们称之为桶，将同一值域的元素存放在同一个桶内并进行桶内排序使其处于有序状态。如果每个桶是有序的，则由这些桶按顺序构成的集合也必定是有序的。

2. 算法步骤

（1）根据待排序序列中元素的分布特征和差值范围，确定映射函数与申请桶的个数。
（2）遍历序列，将每个记录放到对应的桶中。
（3）选取排序方法，对不为空的桶进行内部排序。
（4）把已排序的桶中的元素放回己清空的原序列中。

3.算法分析

其实，对于桶排序的把握还是比较难的，因片桶排序有点像快速排序又有点像计数排序。
桶排序与快速排序的区别如下：

快速排序是两个分区的排序，而桶排序是多个分区；
快速排序是原地排序方式，即在数组本身内进行排序，而桶排序是在申请的额外的操作空间中进行排序；
快速排序中每个分区的排序方式依然是快速排序，而桶排序则可以自主选择恰当的排序算法进行桶内排序。

桶排序与计数排序的区别如下：

计数排序申请空间的跨度是从最小元素到最大元素，受待排序序列范围的影响很大，而桶排序则弱化了这种影响，这样就减少了元素大小不连续时计数排序所存在的空间浪费情况。

总结一下，桶排序有两个关键点：元素值域的划分和排序算法的选择。

元素值域的划分也就是元素到桶的映射规则，需要根据待排序序列的分布特性进行分析和选择。如果规则设计得过于模糊和笼统，所有待排序元素可能会映射到同一个桶中，则桶排序向比较排序算法演变；如果映射规则过于具体和严苛，每一个待排序元素可能会单独映射到一个桶中，则桶排序向计数排序算法演变。
排序算法的选择是指在进行桶内排序时，可以自主选择任意的排序算法。桶排序的复杂度和稳定性根据桶内排序算法的不同而不同。
在桶排序算法中，时间复杂度分为两部分：映射过程和桶内排序及回填数组过程。映射过程涉及每个元素，所以时间复杂度为O(n)；排序过程的时间复杂度是由选取的排序算法和桶的个数决定的，由于这里选取的是堆排序算法，并且有n个待排序元素和m个桶，每个桶中平均有 $\frac{n}{m}$ 个数据，所以时间复杂度为：
$O\{m.\frac{n}{m}log_2\frac{n}{m}+n\}=O(n(log_2n-log_2m)+n)$
当桶数等于元素个数，即 m=n时，桶排序向计数排序演变，推排序不起作用，复杂度为o(n)；当桶数为1，即m=1时，桶排序向比较排序算法演变，对整个集合进行堆排序并回填，复杂度为 $O(n+nlog_2n)$ 。
由于桶排序算法需要额外申请空间进行分桶操作，所以空间复杂度为O(n+m)。显而易见，当待排序元素的差值范围较大时，可能会导致绝大多数桶为全桶的现系。从而造成极大的很费，并且对算法的时间复杂度和空间复杂度都有较大的影响，所以和计数排序一样，桶排序适用于元素值分布较集中的序列，数据均匀分布是最好的。

4. 算法代码

算法代码如下：
Python

# -*- coding: utf-8 -*-def heap_sort(array) :"""这里需要注意两点：（1）递归思想（2）列表切片"""length = len(array)#当数组 array 的长度为1时，说明只有一个元素if length<= 1:#无须排序，直接返回原列表return array# 若存在两个或以上节点else:#调整成大顶堆：按照先从下往上，再从左到右的顺序进行调整# 从最后一个非叶子节点（length//2-1）开始向前遍历，直到根节点for i in range(length//2-1,-1,-1):# //为取整# 当左孩儿大于父节点时if array[2*i+1] > array[i]:#二者交換位置array[2*i+1],array[i]=array[i],array[2*i+1] # 如果右孩儿存在且大于父节点时if 2*i+2 <= length-1:if array[2*i+2]> array[i]:#二者交換位置array[2*i+2],array[i] = array[i], array[2*i+2]'''此处省略重构建过程，对结果并不影响！'''# 将堆顶元素与末尾元素进行交换，使最大元素“沉”到数组末尾array[0],array[length-1] = array[length-1], array[0]#递归调用 heap_sort函数对前n-1个元素进行堆排序并返回排序后的结果b=heap_sort(array[0:length-1])return  b + array[length-1:]#桶排序
def bucket_sort (arr) :maximum, minimum = max (arr), min (arr)# 确定桶的个数buckets = [[] for i in range((maximum-minimum) // 10 + 1)]for i in arr:# 计算各元素所属的桶位index = (i- minimum)// 10# list.append（）—添加元素buckets[index]. append(i)# 将原数组清空arr.clear ()for i in buckets:# 桶内排序—堆排序（详情见堆排列的内容）i = heap_sort(i)# 将已排序的桶重新放回已清空的原数组中arr.extend(i)return arr
#调用 bucket_sort 函数
print(bucket_sort([34, 21, 13, 2,5,1,55,3,1,8]))

Java

    public static void bucketSort(int[] arr) {// 确定最大值和最小值int maximum = Arrays.stream(arr).max().getAsInt();int minimum = Arrays.stream(arr).min().getAsInt();// 初始化桶列表ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();for (int i = 0; i < (maximum - minimum) / 10 + 1; i++) {buckets.add(new ArrayList<>());}// 将元素放入对应的桶中for (int i : arr) {int index = (i - minimum) / 10;buckets.get(index).add(i);}// 清空原数组并初始化计数器Arrays.fill(arr, 0);int insertIndex = 0;// 对每个桶内部进行堆排序（这里假设已经实现了heapSort方法）for (ArrayList<Integer> bucket : buckets) {bucket.sort(null); // 使用自然顺序排序，此处也可以替换为自定义的堆排序实现for (int num : bucket) {// 将已排序的桶中的元素重新放回原数组arr[insertIndex++] = num;}}}@Testvoid contextLoads () {int[] arr = {34, 21, 13, 2, 5, 1, 55, 3, 1, 8};bucketSort(arr);System.out.println(Arrays.toString(arr));}