1, 算法简介
桶排序可以算是最简单快速的排序算法了, 只是限定条件要多一点, 需要事先知晓待排序列的极限值或范围来准备足够的桶.
2, 算法原理
桶排序的原理就是准备足够数量的有序桶(一般用数组实现), 用于标记待排序列的每个元素, 用元素值对应桶下标, 桶里的值代表的是元素对应的值出现的次数, 有一次就在原值上加 1(初始值为 0). 当将所有的待排序列中的元素遍历一遍后, 将其全部标记到桶中, 这时候其实就已经排好序了. 如果我们需要正序排序, 则对桶进行正序遍历, 排除值为 0 的桶, 按顺序和桶中值的个数输出桶的下标值, 即为正序列, 倒序反之.
3, 算法实现
- public class BusketSort {
- public static void sort(int[] ints, Boolean isAsc) {
- int[] basket = new int[101]; // 定义足够大的数组桶
- for (int i : ints) {
- basket[i]++; // 对应元素的桶下标自增
- }
- if (isAsc) {
- for (int i = 0; i <basket.length - 1; i++) {
- if (basket[i]> 0) {
- for (int j = 1; j <= basket[i]; j++) {
- System.out.print(i + " "); // 循环输出桶元素不为 0 的下标值
- }
- }
- }
- } else {
- for (int i = basket.length - 1; i> 0; i--) {
- if (basket[i]> 0) {
- for (int j = 1; j <= basket[i]; j++) {
- System.out.print(i + " "); // 循环输出桶元素不为 0 的下标值
- }
- }
- }
- }
- }
- public static void main(String[] args) {
- int[] ints = {2, 6, 4, 9, 12, 98, 5, 32, 90, 33, 24, 65, 37, 12, 4};
- sort(ints, false);
- }
- }
4, 算法解析
首先我们需要准备一个桶数组, 桶数组的大小为已知的待排序列的范围, 比如我们要对学生的单科成绩 (满分 100) 进行排序, 那么我们就要准备 101 个桶(即定义一个长度为 101 的数组).
然后遍历待排序列, 将与待排元素值一致的桶下标对应的桶的值加 1(初始值为 0), 遍历结束, 其实排序也就完成了.
最后, 我们需要正序排序则, 正序遍历桶输出桶下标, 倒序则倒序遍历桶输出桶下标(需要注意的就是下标输出的次数为下标对应的桶值).
4.1 时间复杂度
桶排序的时间复杂度是 O(m+n), 其中 m 为待排序元素个数, n 为桶数.
4.2 空间复杂度
桶排序的空间复杂度极大, 与待排序的最大元素相关.
5, 总结
从代码实现中我们也可以看出, 桶排序是及其简单的, 唯一的缺陷就是桶的存在及其占用空间, 如果我们要排序的数列只有很少的个数, 但是元素之间相差极大的话, 那么我们就需要准备一个极大的桶, 及其浪费空间资源. 一般情况下我们会在一个桶中存放一个范围之内的元素, 桶中的元素我们可以采用其他的排序算法实现排序. 这样可以极大的降低空间消耗.
桶排序一般适用于如下场景:
数据分布相对较为均匀或者数据范围不大的情况下
特殊场景, 比如需要统计元素的个数的情况, 或者希望通过哈希映射快速获取某些值的情况
来源: https://www.cnblogs.com/V1haoge/p/9045967.html