用Java实现桶排序算法
桶排序核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。每个桶内完成排序后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序序列了。“桶”就是我们存放一组数据的容器。
桶排序过程中存在两个关键环节：
①、元素值域的划分，也即元素到桶的映射规则。映射规则需要根据排序集合的元素分布特性进行选择。若规则设计的过于模糊、宽泛，可能导致排序集合中所有元素全部映射到一个桶上，若映射规则设计的过于具体、严苛，则可能导致排序集合中每一个元素值映射到一个桶上。
②、从待排序集合中元素映射到各个桶上的过程，并不存在元素的比较和交换操作，在对各个桶中元素进行排序时，可以选择合适的排序算法，每个桶的排序算法的复杂度和稳定性，决定了最终的算法复杂度和稳定性。
桶排序的核心思想简单易懂，其代码实现也不难。以下代码递归+桶排序完成桶排序算法实现。
package sort;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class BucketSort {
public List<Integer> bucketSort(List<Integer> list, int bucketSize) {
if (list == null || list.size() <=1 || bucketSize < 1) {
return list;
}
// 确定数组中最大值、最小值
int maxOfArr = list.get(0);
int minOfArr = list.get(0);
for (int i = 0; i < list.size(); i++) {
if (list.get(i) > maxOfArr) {
maxOfArr = list.get(i);
}
else if (list.get(i) < minOfArr) {
minOfArr = list.get(i);
}
}
// 确定桶的个数
int bucketCount = (maxOfArr - minOfArr) / bucketSize + 1;
// 创建一个数组，用来存储所有桶
List<List<Integer>> bucketList = new ArrayList<>();
// 按序将桶添加进去
for (int i = 0; i < bucketCount; i++) {
bucketList.add(new ArrayList<Integer>());
}
// 将排序数组元素按照顺序放入桶中
for(int j = 0; j < list.size(); j++) {
int bucketIndex = (list.get(j) - minOfArr) / bucketSize;
bucketList.get(bucketIndex).add(list.get(j));
}
// 创建一个最终存储结果的列表
List<Integer> resultList = new ArrayList<>();
// 对每一个桶中的数据进行排序
for (int i = 0; i < bucketList.size(); i++) {
// 依次取出每个桶
List<Integer> elementList = bucketList.get(i);
if (elementList.size() > 0) {
// 如果桶内有元素
if (bucketCount == 1) {
// 当只有一个桶时，缩小桶的大小以获得更多的桶
bucketSize--;
}
// 递归调用桶排序为每一个桶进行排序
List<Integer> tempList = bucketSort(elementList, bucketSize);
for (int j = 0; j < tempList.size(); j++) {
resultList.add(tempList.get(j));
}
}
}
return resultList;
}
写一段测试代码进行测试，代码和结果如下。
public void test() {
// 准备一个数组
List<Integer> list = new ArrayList<>();
list.add(3);
list.add(1);
list.add(0);
list.add(6);
list.add(4);
list.add(8);
list.add(9);
list.add(7);
System.out.println("排序前：");
System.out.println(list);
list = bucketSort(list, 3);
System.out.println("排序后：");
System.out.println(list);
}
// 打印结果
排序前：
[3, 1, 0, 6, 4, 8, 9, 7]
排序后：
[0, 1, 3, 4, 6, 7, 8, 9]
最后我们做一个总结：
①、桶排序的时间复杂度，取决于对各个桶之间数据进行排序的时间复杂度，如果我们将待排序元素映射到某一个桶的映射规则做的很好，桶划分的越小、各个桶之间的数据越少，排序所用的时间也会越少。当我们对每个桶采用快速排序时如果桶的个数接近数据规模n时，复杂度为O(n)，在极端情况下复杂度退化为O(nlogn)。
②、桶排序虽然快，但是它其实是采用了用空间换时间的做法。由于需要开辟新的空间保存元素，并申请空间存放每个桶，所以空间复杂度为O(n+m)，m代表桶的个数。
③、桶排序是否稳定取决于每一个桶内排序算法的稳定性，如果使用快速排序就不是一个稳定的排序算法。
今天关于桶排序的分享就到这里了，期待下篇文章见。