Sorting Algorithms:Bucket Sort
前言
该博客用于本弱鸡复习巩固,打牢基础,还望各大佬不吝赐教。
基本思路
桶排序的关键在于如何根据待排序数组设置合理的桶(也看做一个数组)的数量,两个值之间需要寻找一个合理的映射函数,这样才能保证该算法的高效。
如果取到合理的桶值,根据映射函数,我们可以将待排序数组均匀的分到每个桶中,再分别对各个桶中的元素进行排序(每个桶中的排序方式可能也会根据情况而定),最后我们直接输出桶中的数据就好。
桶排序可用于最大最小值相差较大的数据情况,
比如 [9012,19702,39867,68957,83556,102456]。
而且最好数据的分布尽量均匀,否则可能导致数据都集中到一个桶中。
比如 [104,150,123,132,20000],
这种数据会导致前4个数都集中到同一个桶中。导致桶排序失效。
图片示例
算法复杂度分析
桶排序最好情况下使用线性时间O(n),
桶排序的时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,
因为其它部分的时间复杂度都为O(n)。
很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。
但相应的空间消耗就会增大。
代码注释中也标明了用到的排序算法。
代码实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
/**
* Bucket Sort
* 桶排序的关键在于如何根据待排序数组设置合理的桶(也看做一个数组)的数量,
* 两个值之间需要寻找一个合理的映射函数,这样才能保证该算法的高效。
*
* 如果取到合理的桶值,根据映射函数,我们可以将待排序数组均匀的分到每个桶中,
* 再分别对各个桶中的元素进行排序,
* 最后我们直接输出桶中的数据就好。
*
* 桶排序可用于最大最小值相差较大的数据情况,比如[9012,19702,39867,68957,83556,102456]。
* 而且最好数据的分布尽量均匀,
* 否则可能导致数据都集中到一个桶中。比如[104,150,123,132,20000],
* 这种数据会导致前4个数都集中到同一个桶中。导致桶排序失效。
*
* 算法复杂度分析
* 桶排序最好情况下使用线性时间O(n),桶排序的时间复杂度,
* 取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为O(n)。
* 很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。
* 但相应的空间消耗就会增大。
*
*/
public class BucketSort {
public static void main(String[] args) {
int[] a = new int[100];
boolean flag = true;
//random array
for (int i = 0; i < a.length; i++) {
Random rd = new Random();
a[i] = rd.nextInt(1000);
}
System.out.println("Random Array :");
System.out.println(Arrays.toString(a));
System.out.println();
System.out.println("Bucket Sort :");
//桶排序开始
bucketSort(a);
}
public static void bucketSort(int[] a) {
//找到数组的最大值和最小值,用来计算映射函数
//a[0]=0;
int minValue = a[0];
int maxValue = a[0];
for (int i = 0; i < a.length; i++) {
maxValue = Math.max(maxValue, a[i]);
minValue = Math.min(minValue, a[i]);
}
//桶数量的映射函数如下(事先设定好的,也可以试着随便用其他的映射关系看看结果),计算出桶的数量
int bucketSize = (maxValue - minValue) / a.length + 1;
//将整个桶数组用ArrayList表示,每个桶用存放Integer的ArrayList表示
ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketSize);
//初始化桶数组,把每一个桶都初始化为一个ArrayList<Integer>
for (int i = 0; i < bucketSize; i++) {
buckets.add(new ArrayList<Integer>());
}
System.out.println("minValue = " + minValue);
System.out.println("maxValue = " + maxValue);
System.out.println("bucketSize = " + bucketSize);
//根据映射函数实现的对应关系,将属于同一个桶的元素放入对应的桶
for (int i = 0; i < a.length; i++) {
//映射函数实现元素与桶之间的对应
int num = (a[i] - minValue) / a.length;
buckets.get(num).add(a[i]);
}
//对桶进行排序(这里使用了java自带的TimSort算法)
// 时间复杂度平均值=最坏= O(nlogn)) 最好=O(n)
//空间复杂度O(n)
for (int i = 0; i < buckets.size(); i++) {
Collections.sort(buckets.get(i));
}
System.out.println(buckets.toString());
}
}
执行结果
- 在本次代码执行中,设置的是随机生成一个大小为10的数组,元素范围在0-100之间
- 可以看到bucketSize就是桶的数量
- 将排好序的桶链表输出,可以看到每个桶存放的元素数量不一样,这是根据映射函数实现的,但已经完成了对原数组的排序
参考
GeeksforGeeks:https://www.geeksforgeeks.org/bucket-sort-2/
十大经典排序算法:https://www.cnblogs.com/onepixel/articles/7674659.html
计数排序和桶排序(Java实现):https://www.cnblogs.com/zer0Black/p/6169858.html