日常算法——桶排序

序言

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

桶排序

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

代码实现

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