日常算法——桶排序

本贴最后更新于 2555 天前,其中的信息可能已经时移世异

序言

时常动动脑,做做算法题还是挺有意思的,温习下桶排序。

桶排序

桶排序是排序算法中最简单最快的排序算法。主要思想就是,以数组为桶,桶有序号,序号即数组的索引。遍历待排序的数组,把该数值放入与之相等的序号的桶内,然后从桶中取出非零值得下标即可。

代码实现

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 为桶的个数。

  • 算法
    428 引用 • 254 回帖 • 24 关注
  • 排序
    19 引用 • 16 回帖 • 1 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...