序言
时常动动脑,做做算法题还是挺有意思的,温习下桶排序。
桶排序
桶排序是排序算法中最简单最快的排序算法。主要思想就是,以数组为桶,桶有序号,序号即数组的索引。遍历待排序的数组,把该数值放入与之相等的序号的桶内,然后从桶中取出非零值得下标即可。
代码实现
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(){
for (int i = 0; i < array.length; i++) {
buckets[array[i]]++;
}
}
public void print() {
//desc
for (int i = buckets.length - 1; i >= 0; i--) {
for (int j = buckets[i]; j > 0; j--) {
System.out.println(i);
}
}
}
public static void main(String[] args) {
int[] array = {1, 2, 64, 45, 23, 23};
BucketSort bucketSort = new BucketSort(65,array);
bucketSort.sort();
bucketSort.print();
}
}
桶排序优点
快速简单
桶排序缺点
需要知道待排序最大值,并创建一个这么大的数组,如果最大值为 10w 那就 gg 了,所以桶排序是以空间换时间的方式,适合范围比较小的排序
时间复杂度
由于需要遍历所有桶,时间复杂度为 O(n+m),n 为待排序元素个数,m 为桶的个数。
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于