桶排序（Bucket Sort）

一、算法概述

1.1 算法分类

十种常见排序算法可以分为两大类：

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。

• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

1.2 算法复杂度

1.3 相关概念

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

二、桶排序（Bucket Sort）

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

2.1 算法描述

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

2.2 图片演示

三、代码实现

import java.util.*; /** * @Author: huangyibo * @Date: 2022/3/14 15:30 * @Description: 桶排序 */ public class BucketSort { public static void main(String[] args) { int[] arr = {220, 134, 0, 153, 2, 1314, 87, 2022, -8, -99}; bucketSort(arr); System.out.println(Arrays.toString(arr)); } public static void bucketSort(int[] arr) { if (arr == null || arr.length <= 1) { return; } //建立桶，个数和待排序数组长度一样 int len = arr.length; List<Integer>[] bucket = new LinkedList[len]; // 找出待排序数组arr中的最大值 int max = Arrays.stream(arr).max().getAsInt(); //根据每个元素的值, 分配到对应范围的桶中 for (int i = 0; i < arr.length; i++) { int index = toBucketIndex(arr[i], max, len); // 没有桶才建立桶(延时) if (bucket[index] == null) { bucket[index] = new LinkedList<>(); } // 有桶直接使用 bucket[index].add(arr[i]); } // 对每个非空的桶排序，排序后顺便存入临时的List，则list中已经有序） List<Integer> temp = new ArrayList<>(); for (int i = 0; i < len; i++) { if (bucket[i] != null) { Collections.sort(bucket[i]); temp.addAll(bucket[i]); } } // 将temp中的数据写入原数组 for (int i = 0; i < len; i++) { arr[i] = temp.get(i); } } /** * 映射函数，将值转换为应存放到的桶数组的索引 * @param value * @param maxValue * @param length * @return */ private static int toBucketIndex(int value, int maxValue, int length) { return (value * length) / (maxValue + 1); } }

四、算法分析

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n2)

参考： https://www.cnblogs.com/onepixel/articles/7674659.html

https://blog.csdn.net/ThinkWon/article/details/101544356