桶排序和基数排序

前言：

这篇文章，我们就来了解一些鲜为人知的排序，桶排序和基数排序。

桶排序：

桶排序的思想：

桶排序的思想就是把待排序的数尽量均匀地放到各个桶中，再对各个桶进行局部的排序，最后再按序将各个桶中的数输出，即可得到排好序的数。

桶排序（Bucket Sort）又称箱排序，是一种比较常用的排序算法。其算法原理是将数组分到有限数量的桶里，再对每个桶分别排好序（可以是递归使用桶排序，也可以是使用其他排序算法将每个桶分别排好序），最后一次将每个桶中排好序的数输出。

首先确定桶的个数。因为桶排序最好是将数据均匀地分散在各个桶中，那么桶的个数最好是应该根据数据的分散情况来确定。首先找出所有数据中的最大值max和最小值min；

求桶的个数：

根据max和min确定每个桶所装的数据的范围 size，有size = (max - min) / n + 1，n为数据的个数，需要保证至少有一个桶，故而需要加个1；

求桶数据范围差值：

求得了size即知道了每个桶所装数据的范围，还需要计算出所需的桶的个数count，有
count = (max - min) / size + 1，需要保证每个桶至少要能装1个数，故而需要加个1；

桶的数据范围：

求得了size和cnt后，即可知第一个桶装的数据范围为 [min, min + size)，第二个桶为 [min + size, min + 2 * size)，…，以此类推。

因此步骤2中需要再扫描一遍数组，将待排序的各个数放进对应的桶中。

对桶中的元素进行排序：

对各个桶中的数据进行排序，可以使用其他的排序算法排序，例如快速排序；也可以递归使用桶排序进行排序；

统一排序：

最后将各个桶中排好序的数据依次输出，最后得到的数据即为最终有序。

图解：

接下来举一个例子：

例如，待排序的数为：3, 6, 9, 1

1）求得 max = 9，min = 1，n = 4
size = （9 - 1) / n + 1 = 3
count = (max - min) / size + 1 = 3

2）由上面的步骤可知，共3个桶，每个桶能放3个数，第一个桶数的范围为 [1, 4)，第二个[4, 7)，第三个[7, 10)
扫描一遍待排序的数，将各个数放到其对应的桶中，放完后如下图所示：

3）对各个桶中的数进行排序，得到如下图所示：

4）依次输出各个排好序的桶中的数据，即为：1, 3, 6, 9
可见，最终得到了有序的排列。

代码：

    public static void barrelSort(int[] nums) {
        int n = nums.length;
        int max = 0, min = 0;

        //找出最大最小值
        for (int i = 0; i < n; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
            if (nums[i] < min) {
                min = nums[i];
            }
        }

        int size = (max - min) / n + 1;//获取桶的个数，至少保证有一个
        int count = (max - min) / size + 1;//得知每个桶中存取数据范围(相当于差值)

        List<Integer>[] barrel = new List[size];//初始化每个桶
        for (int i = 0; i < size; i++) {
            barrel[i] = new ArrayList<>();
        }

        //扫描一遍数组，把数放在对应的桶里面
        for (int i = 0; i < n; i++) {
            int index = (nums[i] - min) / size;//定位第几个桶
            barrel[index].add(nums[i]);
        }

        //对同种每个数据进行排序，这里使用快排
        for (int i = 0; i < size; i++) {
            barrel[i].sort(null);//默认就是升序排序，不需要使用比较器
        }

        //一次出桶
        int index = 0;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < barrel[i].size(); j++) {
                nums[index++] = barrel[i].get(j);
            }
        }

    }
    public static void main(String[] args) {
        int[] nums = {19,27,35,43,31,22,54,66,78};
        barrelSort(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }

    }
}