桶排序(Bucket Sort)是一种排序算法,通常用于将一组数据分割成有限数量的桶(或容器),然后对每个桶中的数据进行排序,最后将这些桶按顺序合并以得到排好序的数据集。
图片
图示如下:
图片
桶排序适用于以下情况:
以下是使用 Java 实现桶排序的示例代码,其中每个桶中的元素排序使用的是快速排序,快速排序的详解请参考历史博文 深入了解快速排序:原理、性能分析与 Java 实现:
public class Test {
public static void mAIn(String[] args) {
int[] arr = new int[]{17,35,37,32,63,46,24};
System.out.println("原始数组:"+ Arrays.toString(arr));
bucketSort(arr);
System.out.println("排序后的数组:"+ Arrays.toString(arr));
}
//桶排序
public static void bucketSort(int[] arr){
int maxVal = Arrays.stream(arr).max().getAsInt();
int minVal = Arrays.stream(arr).min().getAsInt();
//计算桶的数量,+1 是保证至少有1个桶来装数据
int bucketCount = (maxVal - minVal)/arr.length + 1;
// 用于存储每个桶中元素的出现次数
int[] order = new int[bucketCount];
// 用于存储每个桶中的数据
int[][] output = new int[bucketCount][arr.length];
int len = arr.length;
//每个桶中数据的范围,+1 是至少每个桶中的数据范围为1
int rang = (maxVal - minVal)/bucketCount +1;
//将待排序的数组中的所有元素放入到桶中
for(int i = 0; i < len; i++ ){
//计算数组元素所在的桶
int index = (arr[i] - minVal) / rang ;
//将元素放入指定的桶
output[index][order[index]] = arr[i];
//添加桶元素的计数
order[index]++;
}
System.out.println("桶计数数组为:"+ Arrays.toString(order));
int k = 0;
//遍历桶,将桶中的元素放入源数组中,并对其进行快速排序
for(int i = 0; i < bucketCount; i++){
int j ;
if(order[i] > 0){
// 将桶中的元素放入源数组中
for(j = 0; j < order[i]; j++){
arr[k++] = output[i][j];
}
//对桶中的元素进行快速排序
quickSort(arr,k-j,k-1);
}
}
}
//快速排序的详解请参考历史博文 `深入了解快速排序:原理、性能分析与 Java 实现`
public static void quickSort(int[] arr,int left,int right) {
//递归结束条件left < right
if(left < right){
// 通过分区函数得到基准元素的索引
int pivotIndex = partition(arr, left, right);
//递归对基准元素左边的子数组进行快速排序
quickSort(arr,left,pivotIndex-1);
//递归对基准元素右边的子数组进行快速排序
quickSort(arr,pivotIndex+1,right);
}
}
public static int partition(int[] arr,int left,int right) {
// 选择最后一个元素作为基准元素
int pivot = arr[right];
int i = left;
//循环数组,如果满足条件,则将满足条件的元素交换到arr[i],同时i++,循环完成之后i之前的元素则全部为小于基准元素的元素
for (int j = left; j < right; j++) {
if(arr[j] < pivot){
if(j != i){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
i++;
}
}
// 交换 arr[i] 和基准元素
int temp = arr[i];
arr[i] = arr[right];
arr[right] = temp;
//返回基准元素的下标
return i;
}
}
输出结果为:
原始数组:[17, 35, 37, 32, 63, 46, 24]
桶计数数组为:[1, 1, 3, 0, 1, 0, 1]
排序后的数组:[17, 24, 32, 35, 37, 46, 63]
这是一个基本的桶排序实现示例。您可以根据实际需求和数据类型进行扩展和优化。
总的来说,桶排序是一种简单但有效的排序算法,特别适用于某些特定范围内数据的排序,当数据分布均匀时,性能较好。然而,对于不均匀分布的数据,其性能可能下降,因此在实际应用中需要谨慎选择。