Java算法 -- 桶排序
2023-09-14 09:00:30 时间
桶排序(Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶里。每个桶再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间((大O符号))。但桶排序并不是比较排序,他不受到
下限的影响。
桶排序以下列程序进行:
- 设置一个定量的数组当作空桶子。
- 寻访序列,并且把项目一个一个放到对应的桶子去。
- 对每个不是空的桶子进行排序。
- 从不是空的桶子里把项目再放回原来的序列中。
public class BucketSort {
private int[] buckets;
private int[] array;
public BucketSort(int range, int[] array) {
this.buckets = new int[range];
this.array = array;
}
/*排序*/
public void sort() {
if (array != null && array.length > 1) {
for (int i = 0, arrayLength = array.length; i < arrayLength; i++) {
int i1 = array[i];
buckets[i1]++;
}
}
}
/*排序输出*/
public void sortOut() {
//倒序输出数据
// for (int i=buckets.length-1; i>=0; i--){
// for(int j=0;j<buckets[i];j++){
// System.out.print(i+"\t");
// }
// }
for (int i = 0; i <= buckets.length - 1; i++) {
for (int j = 0; j < buckets[i]; j++) {
System.out.print(i + "\t");
}
}
}
public static void main(String[] args) {
testBucketsSort();
}
private static void testBucketsSort() {
int[] array = {5, 7, 17, 3, 5, 22, 4, 15, 8, 6, 4, 1, 2};
BucketSort bs = new BucketSort(23, array);
bs.sort();
bs.sortOut();//输出打印排序
}
}
桶排序特点:
- 速度快简单
- 空间利用率低
桶排序适用场景:
数据范围局限或者有特定要求,范围过大,不推荐适用桶算法。
相关文章
- Java实现 蓝桥杯 算法提高 歌唱比赛(暴力)
- Java实现 蓝桥杯 算法训练 第五次作业:字符串排序
- Java实现蓝桥杯算法提高12-2扑克排序
- Java实现高效便捷还容易懂的排序算法
- Java实现 蓝桥杯 算法提高 成绩排序2
- Java实现完美洗牌算法
- java算法集训代码填空题练习2
- Java实现 蓝桥杯VIP 算法提高 交换Easy
- Java实现 蓝桥杯VIP 算法提高 插入排序
- Java实现 蓝桥杯VIP 算法提高 选择排序
- Java实现 蓝桥杯VIP 算法提高 铺地毯
- Java实现 蓝桥杯VIP 算法提高 能量项链
- Java实现 蓝桥杯VIP 算法提高 贪吃的大嘴
- Java实现 蓝桥杯VIP 算法提高 勾股数
- Java实现 蓝桥杯VIP 算法训练 排列问题
- Java实现 蓝桥杯VIP 算法训练 快速排序
- Java实现 蓝桥杯VIP 算法训练 装箱问题
- Java蓝桥杯 算法提高 九宫格
- Java实现 蓝桥杯 算法提高 最大乘积
- Java实现 蓝桥杯 算法提高 周期字串
- Java 蓝桥杯 算法训练 字符串的展开 (JAVA语言实现)
- Java算法 -- 桶排序
- 【学习总结】java数据结构和算法-第三章-稀疏数组和队列
- 用Java来写常见的排序算法
- Java排序算法--选择排序算法