桶排序又叫箱排序,是计数排序的升级版,它的工作原理是将数组分到有限数量的桶子里,然后对每个桶子再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序),最后将各个桶中的数据有序的合并起来。
- 计数排序是桶排序的一种特殊情况,可以把计数排序当成每个桶里只有一个元素的情况。
链接: 计数排序.
条件
要求输入的数据必须是有确定范围的整数。
适用场景
桶排序可用于最大最小值相差较大的数据情况,但桶排序要求数据的分布必须均匀,否则可能导致数据都集中到一个桶中。
- 比如[104,150,123,132,20000], 这种数据会导致前4个数都集中到同一个桶中。
算法描述
- 找出待排序数组中的最大值max、最小值min
- 我们为待排元素值指定区间构造一个桶(链表构造),桶里放的是待排数组中符合该区间的元素指针
- 桶的数量为(max-min)/arr.length+1
- 遍历数组 arr,计算每个元素 arr[i] 将要放的桶
- 每个桶各自排序
- 遍历桶数组,把排序好的元素放进输出数组
算法实现
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<Integer>());
}
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());
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)