每日一算法|桶排序---第十天
桶排序
水桶的桶
算法
原理
桶排序在某些情况下被认为是最快的排序算法。桶排序(Bucket sort)是一种基于计数的排序算法（计数排序可参考上节的内容），工作的原理是将数据分到有限数量的桶子里，然后每个桶再分别排序。
设置固定数量的空桶。
把数据放到对应的桶中。
对每个不为空的桶中数据进行排序。
拼接不为空的桶中数据，得到结果。
桶排序，就跟我们按某种标准分组一样，比如身高，成绩等等。从小到大排列，在一定的范围内成为一个桶，把范围内的数据都放进来，再按照大小顺序输出就可以了。桶排序理解起来并不难，接下来我们对动图中的数列进行讲解
原始数组{7，12，56，23，19，33，35，42，42，2，8，22，39，26，17}
1.首先，设置固定数量的空桶，在这里为了方便演示，设置桶的数量为 5 个空桶
2.遍历整个数列，找到最大值为 56 ，最小值为 2 ，每个桶的范围为（ 56 - 2 + 1 ）/ 5 = 11，分成5个桶（2，13），[13，24)，[24，35)，[35，46），[46，57）。
3.再次遍历整个数列，按照公式 floor((数字 – 最小值) / 11) 将数字放到对应的桶中，可以理解成求余。
4.比如，数字 7 代入公式 floor((7 – 2) / 11) = 0 放入 0 号桶
5.数字 12 代入公式 floor((12 – 2) / 11) = 0 放入 0 号桶
6.数字 56 代入公式 floor((56 – 2) / 11) = 4 放入 4 号桶
7.当向同一个索引的桶，第二次插入数据时，判断桶中已存在的数字与新插入数字的大小，按照左到右，从小到大的顺序插入（可以使用前面讲解的插入排序）实现
8.比如，插入数字 19 时， 1 号桶中已经有数字 23 ，在这里使用插入排序，让 19 排在 23 前面
9.遍历完整个数列后，合并非空的桶，按从左到右的顺序合并0，1，2，3，4桶。
10.这样就完成了 桶排序
桶排序的优点就是--快。你分的桶越多，排序就越快。但它的缺点也是显而易见的，就是非常消耗空间。这也好理解，你家桶越多，占的地越多嘛。所以不能因为它快就都用它，还得考虑空间资源。
C语言
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<math.h>
#define max(a,b)a>b?a:b
#define min(a,b)a>b?b:a
using namespace std;
int main()
{
int test;
scanf("%d",&test);
while(test--)
{
int n,i,j=0,t;
int b[10001];
scanf("%d",&n);//输入想要排序的数的个数
memset(b,0,sizeof(b));//对b数组初始化
for(i=1; i<=n; i++)
{
scanf("%d",&t);//输入要排序的数
b[t]++;//将某个数出现的次数记录下来例如输入1，1将被存入b[1]这个数组中
}
for(i=0; i<10001; i++)//从b[0]开始输出
{
for(j=1; j<=b[i]; j++)//输出该数的个数
printf("%d ",i);
}
}
return 0;
}
Java
public class BucketSort implements IArraySort {
private static final InsertSort insertSort = new InsertSort();
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
return bucketSort(arr, 5);
}
private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
if (arr.length == 0) {
return arr;
}
int minValue = arr[0];
int maxValue = arr[0];
for (int value : arr) {
if (value < minValue) {
minValue = value;
} else if (value > maxValue) {
maxValue = value;
}
}
int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
int[][] buckets = new int[bucketCount][0];
// 利用映射函数将数据分配到各个桶中
for (int i = 0; i < arr.length; i++) {
int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
buckets[index] = arrAppend(buckets[index], arr[i]);
}
int arrIndex = 0;
for (int[] bucket : buckets) {
if (bucket.length <= 0) {
continue;
}
// 对每个桶进行排序，这里使用了插入排序
bucket = insertSort.sort(bucket);
for (int value : bucket) {
arr[arrIndex++] = value;
}
}
return arr;
}
/**
* 自动扩容，并保存数据
*
* @param arr
* @param value
*/
private int[] arrAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
}
Python
// An highlighted block
def bucketSort(nums):
max_num = max(nums)
# 创建一个元素全是 0 的列表， 当做桶
bucket = [0]*(max_num+1)
print(bucket)
# 把所有元素放入桶中， 即把对应元素个数加一
for i in nums:
bucket[i]+=1
# 存储排序好的元素
sort_nums = []
# 取出桶中的元素
for j in range(len(bucket)):
if bucket[j]!=0:
for y in range(bucket[j]):
sort_nums.append(j)
return sort_nums
nums = [5,6,3,2,1]
print(bucketSort(nums))