排序算法之桶排序

公告：“业余草”微信公众号提供免费CSDN下载服务(只下Java资源)，关注业余草微信公众号，添加作者微信：xttblog2，发送下载链接帮助你免费下载！
本博客日IP超过2000，PV 3000 左右，急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包，请加博主新的微信号：xttblog2，之前的微信号好友位已满，备注：返现
受密码保护的文章请关注“业余草”公众号，回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽，请关注文末小程序

腾讯云】1核2G5M轻量应用服务器50元首年，高性价比，助您轻松上云

桶排序（Bucket sort）也有人叫做所谓的箱排序。听过的人可能不多，名气不大，但它却是 10 大排序算法中的一部分，足见得它的重要性。今天我们一起来聊聊它。

桶排序的工作原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间。但桶排序并不是比较排序，他不受到O(n log n) 下限的影响。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

为了使桶排序更加高效，我们需要做到这两点：

• 在额外空间充足的情况下，尽量增大桶的数量
• 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

排序过程：

1. 设置一个定量的数组当作空桶子。
2. 寻访序列，并且把项目一个一个放到对应的桶子去。
3. 对每个不是空的桶子进行排序。
4. 从不是空的桶子里把项目再放回原来的序列中。

桶排序的 Java 案例代码如下所示：

private int indexFor(int a, int min, int step) {
    return (a - min) / step;
}
public void bucketSort(int[] arr) {
    int max = arr[0], min = arr[0];
    for (int a : arr) {
        if (max < a)
            max = a;
        if (min > a)
            min = a;
    }
    // 该值也可根据实际情况选择
    int bucketNum = max / 10 - min / 10 + 1;
    List buckList = new ArrayList<List<Integer>>();
    // create bucket
    for (int i = 1; i <= bucketNum; i++) {
        buckList.add(new ArrayList<Integer>());
    }
    // push into the bucket
    for (int i = 0; i < arr.length; i++) {
        int index = indexFor(arr[i], min, 10);
        ((ArrayList<Integer>) buckList.get(index)).add(arr[i]);
    }
    ArrayList<Integer> bucket = null;
    int index = 0;
    for (int i = 0; i < bucketNum; i++) {
        bucket = (ArrayList<Integer>) buckList.get(i);
        insertSort(bucket);
        for (int k : bucket) {
            arr[index++] = k;
        }
    }
}
// 把桶內元素插入排序
private void insertSort(List<Integer> bucket) {
    for (int i = 1; i < bucket.size(); i++) {
        int temp = bucket.get(i);
        int j = i - 1;
        for (; j >= 0 && bucket.get(j) > temp; j--) {
            bucket.set(j + 1, bucket.get(j));
        }
        bucket.set(j + 1, temp);
    }
}

排序动态效果图如下所示：

假设数据是均匀分布的，则每个桶的元素平均个数为n/k。假设选择用快速排序对每个桶内的元素进行排序，那么每次排序的时间复杂度为O(n/klog(n/k))。总的时间复杂度为O(n)+O(m)O(n/klog(n/k))=O(n+nlog(n/k))=O(n+nlogn-nlogk。当k接近于n时，桶排序的时间复杂度就可以金斯认为是O(n)的。即桶越多，时间效率就越高，而桶越多，空间就越大。

最后，欢迎关注我的个人微信公众号：业余草（yyucao）！可加作者微信号：xttblog2。备注：“1”，添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注！后续有精彩内容会第一时间发给您！原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系！

本文原文出处：业余草： » 排序算法之桶排序