桶排序

原理

• 适合待排序数据值域较大但分布比较均匀的情况

• 步骤

  • 设置一个定量的数组当空桶
  • 遍历序列，并将元素一个个放到对应的桶中
  • 对每一个不是空的桶进行排序
  • 从不是空的桶里把元素再放回到原来的序列中

    性质

• 稳定性 ： 当内层排序稳定时，并且将元素插入桶中时不改变元素间的相对顺序，那么桶排序就是一种稳定的排序算法。每块元素不多，一般使用插入排序，此时稳定

• 时间复杂度
  • 平均复杂度：
  • 最坏复杂度：

    代码

    public void bucket_sort(int[] a) {
    final int BUCKET_NUM = 100;
    ArrayList<Integer>[] bucket = new ArrayList[BUCKET_NUM];
    for (int i = 0; i < bucket.length; i++) {
       bucket[i] = new ArrayList<>();
    }
    for (int i = 0; i < a.length; i++) {
       bucket[a[i] / 100].add(a[i]);
    }
    int num = 0;
    for (int i = 0; i < bucket.length; i++) {
       Integer[] integers = bucket[i].toArray(new Integer[bucket[i].size()]);
       insertion_sort(integers);
       for (int j = 0; j < integers.length; j++) {
           a[num++] = integers[j];
       }
    }
    }