桶排序是一种分配式排序算法，将元素分到有限数量的桶里，每个桶再单独排序（比如用插入排序），最后依次把各个桶中的元素取出来即完成排序。
时间复杂度：最佳 O(n) | 平均 O(n + n²/k + k) | 最差 O(n²)
空间复杂度:O(n + k)
稳定性:稳定
应用场景/前提条件
- 适合均匀分布的数据
- 需要额外空间
- 可以与其他排序算法结合
介绍
桶排序（Bucket Sort）是一种分布式排序算法，核心思想是将数据分散到有限数量的桶中，然后对每个桶中的数据进行排序，最后将各个桶中的数据有序地合并起来。桶排序是计数排序的扩展版本，特别适合均匀分布的数据集。
桶排序的效率取决于数据分布的均匀性。在最佳情况下，桶排序的时间复杂度可以达到 O(n)，在特定场景下非常高效。桶排序结合了哈希表的思想，通过映射函数将元素分配到不同的桶中实现排序
算法步骤
- 确定桶的数量和范围，创建对应数量的桶（通常是数组或链表）
- 根据映射函数将每个元素分配到对应的桶中
- 对每个桶内的元素分别进行排序（可以使用任何排序算法）
- 按照桶的顺序将各个桶中的元素依次取出，组成有序序列
代码实现如下（浮点类型）：
public static void main(String[] args) {
float[] nums = {0.23f,1f,0.82f,0f,1.2f,999f};
handleData(nums);
for (Float num : nums){
System.out.println( num+" ");
}
}
public static void handleData(float[] nums){
//获取最大最小数
float max = nums[0];
float min = nums[0];
for(float num : nums){
if(num> max){
max = num;
}
if(num<min){
min = num;
}
}
//初始化桶
List<List<Float>> list = new ArrayList<>();
for(int i = 0; i< nums.length;i++){
list.add(new ArrayList<>());
}
//桶范围设置
int step = (int)Math.ceil((double)(max-min)/(nums.length));
//将元素放入桶中
for(float num : nums){
int index = (int)(num - min) / step;
//处理临界桶
if(index == nums.length){
index--;
}
list.get(index).add(num);
}
//桶中元素排序
for(List<Float> key: list){
for(int i = 1; i< key.size(); i++){
float key1 = key.get(i);
int j = i-1;
while(j>=0&&key.get(j)>key1){
key.set(j+1, key.get(j));
j--;
}
key.set(j+1, key1);
}
}
//将元素重新放回数值中
int i = 0;
for(List<Float> key: list){
for(Float index: key){
nums[i++] = index;
}
}
}代码实现如下（整数类型）：
public static void main(String[] args) {
int[] nums = {2,6,6,8,9,7,3,4,44,15,22};
handleData1(nums);
for (int num : nums){
System.out.println( num+" ");
}
}
public static void handleData1(int[] nums){
//获取最大最小数
int max = nums[0];
int min = nums[0];
for(int num : nums){
if(num> max){
max = num;
}
if(num<min){
min = num;
}
}
//初始化桶
List<List<Integer>> list = new ArrayList<>();
for(int i = 0; i< nums.length;i++){
list.add(new ArrayList<>());
}
//桶范围计算-最大值-最小值/数组长度，再向上取整
int step = (int)Math.ceil((double)(max-min)/(nums.length));
//将元素放入桶中
for(int num : nums){
int index = (num - min) / step;
if(index == nums.length){
index--;
}
list.get(index).add(num);
}
//桶中元素排序--插入算法
for(List<Integer> key: list){
for(int i = 1; i< key.size(); i++){
int index= key.get(i);
int j = i-1;
while(j>=0 && key.get(j)>index){
key.set(j+1,key.get(j));
j--;
}
key.set(j+1,index);
}
}
//将元素重新放回数值中
int i = 0;
for(List<Integer> key: list){
for(Integer index: key){
nums[i++] = index;
}
}
}以上代码实现是根据个人理解情况，按思路写的实现流程，还要许多可优化的地方，如桶个数、桶的数据范围，都是可以优化的颠；
注意实际的算法中，还需要注意特殊情况的处理，如算法题：
164. 最大间距 - 力扣（LeetCode）
个人算法题解如下：
if(nums.length <2){
return 0;
}
int k = handleData(nums);
if (k ==0){
return 0;
}
//最大差值
int num = 0;
for(int i =0; i<nums.length-1; i++){
if ((nums[i+1]-nums[i])>num){
num = nums[i+1]-nums[i];
}
}
return num;
}
public int handleData(int[] nums){
//获取最大最小数
int max = nums[0];
int min = nums[0];
for(int num : nums){
if(num> max){
max = num;
}
if(num<min){
min = num;
}
}
if(max-min == 0){
return 0;
}
//初始化桶
List<List<Integer>> list = new ArrayList<>();
for(int i = 0; i< nums.length;i++){
list.add(new ArrayList<>());
}
//桶范围设置
int step = (int)Math.ceil((double)(max-min)/(nums.length));
//将元素放入桶中
for(int num : nums){
//int index = (int)((num-min)/step*(backetCount-1));
int index = (num - min) / step;
if(index == nums.length){
index--;
}
list.get(index).add(num);
}
//桶中元素排序
for(List<Integer> key: list){
for(int i = 1; i< key.size(); i++){
if(key.get(i-1)>key.get(i)){
Integer temp = key.get(i);
key.set(i,key.get(i-1));
key.set(i-1,temp);
}
}
}
//将元素重新放回数值中
int i = 0;
for(List<Integer> key: list){
for(Integer index: key){
nums[i++] = index;
}
}
return 1;
}