排序——桶排序（Bucket sort）

Bucket sort）"/>

排序——桶排序（Bucket sort）

算法思路

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

算法详解

桶排序的思想近乎彻底的分治思想。算法的过程描述如下：

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

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

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

下面我们用一个实例来说明。待排序集合为：[-7, 51, 3, 121, -3, 32, 21, 43, 4, 25, 56, 77, 16, 22, 87, 56, -10, 68, 99, 70]，映射规则为：，其中常量位：，即以间隔大小 10 来区分不同值域。

第一步

遍历集合可得，最大值为：，最小值为：，待申请桶的个数为：。

第二步

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

第三步

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

图解算法

动画展示

感谢五分钟学算法制作的GIF图片。

算法性能

时间复杂度

k 表示桶的个数。

平均时间复杂度：O(n+k)。

最佳时间复杂度：O(n+k)。

最差时间复杂度：。

空间复杂度

O(n+k)。k 表示桶的个数。

稳定性

算法的稳定性取决于对桶中元素排序时选择的排序算法。

代码实现

C++

const int offset = 105; // 为桶的边界template <typename T>
void BucketSort(T arr[], int n) {int i, j;T buckets[offset];for(i = 0; i < offset; i++) // 清零buckets[i] = 0;// 1.计数,将数组arr中的元素放到桶中for(i = 0; i < n; i++)buckets[arr[i]]++; // 将arr[i]的值对应buckets数组的下标，每有一个就加1// 2.排序for(i = 0, j = 0; i < offset; i++) {while(buckets[i] > 0) { // 说明存有元素,相同的整数，要重复输出arr[j] = i;buckets[i]--;j++;}}
}

Java

public static void bucketSort(int[] arr){// 计算最大值与最小值int max = Integer.MIN_VALUE;int min = Integer.MAX_VALUE;for(int i = 0; i < arr.length; i++){max = Math.max(max, arr[i]);min = Math.min(min, arr[i]);}// 计算桶的数量int bucketNum = (max - min) / arr.length + 1;ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);for(int i = 0; i < bucketNum; i++){bucketArr.add(new ArrayList<Integer>());}// 将每个元素放入桶for(int i = 0; i < arr.length; i++){int num = (arr[i] - min) / (arr.length);bucketArr.get(num).add(arr[i]);}// 对每个桶进行排序for(int i = 0; i < bucketArr.size(); i++){Collections.sort(bucketArr.get(i));}// 将桶中的元素赋值到原序列int index = 0;for(int i = 0; i < bucketArr.size(); i++){for(int j = 0; j < bucketArr.get(i).size(); j++){arr[index++] = bucketArr.get(i).get(j);}}  
}

Python

     def __init__(self, datas, size=100):self.datas = datasself.bucketSize = sizeself.result = [0 for i in range(len(datas))]self.bucket = [0 for i in range(self.bucketSize)]def _sort(self):# 读入各个元素，并在对应的位置统计，当bucket里的元素不为0# 就保存到result里面for num in self.datas:self.bucket[num] += 1j = 0for i in range(self.bucketSize):while(self.bucket[i]):self.result[j] = iself.bucket[i] -= 1j += 1def show(self):print "Resutl is:",for i in self.result:print i,print ''