桶排序(Bucket Sort)
1. 什么是桶排序
桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的要害就在于这个映射函数的确定。为了使桶排序更加高效,咱们须要做到这两点:
- 在额定空间短缺的状况下,尽量增大桶的数量
- 应用的映射函数可能将输出的 N 个数据平均的调配到 K 个桶中
同时,对于桶中元素的排序,抉择何种比拟排序算法对于性能的影响至关重要。
2. 算法解释
- 什么时候最快
当输出的数据能够平均的调配到每一个桶中。
- 什么时候最慢
当输出的数据被调配到了同一个桶中。
- 示意图
元素散布在桶中:
而后,元素在每个桶中排序:
3. 代码实现
public class BucketSort {public static void main(String[] args) {
// 初始化数组
int[] arr = {5, 3, 1, 4, 2, 7, 8, 6, 10, 9};
bucketSort(arr);
}
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<>());
}
// 将每个元素放入桶
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));
}
System.out.println(bucketArr.toString());
}
}
4. 输入后果
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]