简介

十大经典排序算法里面冒泡、插入、选择排序时间为O（$n^2$)，归并、快排、堆排序这些排序时间为O(nlogn)，此外还有三种更快的排序算法为桶排序，基数排序，计数排序。后面这三种排序时间为O(n)，因此也被称之为线性排序算法。

桶排序一般是分这几步来操作：

0. 先定义一组或者说几个有序的“桶”
1. 使用映射函数将数组内的数据映射到各自对应的“桶”内
2. 在每个“桶”内进行排序（归并、插入、快排等等都可以）
3. 按顺序将每个”桶“内的数据依次取出，就可以输出一个有序的数组/数列

尝试实现

输入数组为：40，55，10，64，2，71，90，25，81，43

2.1 创建有序”桶“

”桶“一般我们采用二维的数组来实现。考虑到数组还要扩容，所以在Java端直接用ArrayList来做即可。

ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();

另外一个就是桶的个数。很多例子中都是给个默认大小5，开始时先遍历一遍数组，找出最大值和最小值。然后根据(max-min)/5 + 1来计算出桶的个数。我们这里做简化处理，因为知道输入数组元素值得范围大致为0到99，可以按0-9,10-19...90-99这样划分为10组，所以取桶的个数为10。

2.2 映射函数

这一步的映射函数的作用是根据数组中的元素值，计算出它应该被归类为哪个桶，也就是计算出桶的下标值。

上一步中知道是划分为10组，所以映射函数可以简单写为int index = item/10。

2.3 桶内排序

桶内排序可以采用冒泡、插入等等算法来实现，我们也是简化处理直接调用系统API来实现```

2.4 整理数据

这一步最简单，按桶的编号从0到9将各自里面的数据拿出来回写到输入数组中即可。

代码实现

public static void bucketSort(int[] nums) {
    if (null == nums || 1 == nums.length) {
        return;
    }
    //第一步,创建桶
    ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();
    int bucketSize = 10;
    for(int i=0;i<bucketSize;i++){
        buckets.add(new ArrayList<>());
    }

    //第二步使用映射函数将数据分到各自的桶里面
    for (int i = 0; i < nums.length; i++) {
        int index = nums[i] / 10;
        buckets.get(index).add(nums[i]);
    }

    //第三步,将各个桶内的元素进行排序
    for (int i = 0; i < bucketSize; i++) {
        Collections.sort(buckets.get(i));
    }

    //第四步,按顺序将每个桶内的元素读取回写到nums中
    int index = 0;//回写时用的游标
    for (int i = 0; i < bucketSize; i++) {
        for (int j = 0; j < buckets.get(i).size(); j++) {
            nums[index++] = buckets.get(i).get(j);
        }
    }
}

算法分析

时间复杂度

假如要排序n个数字，桶的个数取m，每个桶里面元素个数为s=$n/m$。每个桶采用标准API进行排序（标准api的实现一般都是快排的改进版）排序时间复杂度为O(slogs)。换算一下就是O((n/m*m)logn/m)=O(nlogn/m)。理想状态下桶的个数m的值接近n的大小，logn/m可以看成是个常量。所以可以近似的认为桶排序的时间复杂度为O(n)。

最坏情况下，数据没有均匀的分布而是被集中到了一个桶里面，那桶排序的时间就会退化为O(nlogn)

空间复杂度

已上过程中我们知道桶排序是借助了若干个桶的空间来实现的，所以它的空间复杂度为O(m)。m为桶的个数。

稳定性

关于稳定性我们知道同一个算法由于我们不同的实现会导致它从一个稳定的排序算法变为不稳定的排序算法。

按桶排序的过程我们知道，相同大小的元素会按自己的原始顺序，先后落入相同编号的桶内。如果桶内排序采用的是稳定的排序算法，那么输出的顺序肯定和之前的一样不会发生变化。因此桶排序是个稳定的排序算法。

备注

虽然桶排序的性能优异，但是并不能替代快排、归并等等这些算法。原因在于桶排序的特殊要求：1.它需要将待排序的元素均匀的划分到m个桶内；2.桶和桶之间是天然排好序的，这样各个桶内元素排好序后，桶和桶之间是不需要进行排序的。而大部分情况下，元素很难做到均匀分布到各个桶内。所以它有一个很明显的缺点，空间利用率低。

综上，桶排序一般适用于元素大小范围跨度不大，分布比较均匀的情况下。另外就是外排序，比如有十几个G这样的数据，一次性很难加载到内存中。比较适合采用桶排序。先对数据进行划分，然后每个小块加载到内存中进行排序，进而完成整体数据的排序操作。

这是我的公众号欢迎大家关注：