【十大经典排序算法】：桶排序及其JAVA代码实现

对于排序算法，相信每一个接触过编程的人都不会陌生，从最初在大学学习的冒泡排序、快速排序、选择排序到后来接触的归并排序、基数排序、桶排序...排序算法应该是实际编程中用得最多的算法之一。

原理

现在我们来看看排序算法中的桶排序，顾名思义，桶排序即通过桶来完成排序；首先我们应当获取排序数组中的最大值min与最小值max，然后根据最大值最小值来定义k个桶（即将最大值最小值之间的数k等分），每个桶用于放置指定范围的值，之后对每个桶进行单独排序，然后根据桶的顺序及桶中值的顺序进行排序即可得到原数组的排序结果。

示意图

可能上面这一堆文字介绍让人感到懵逼，但是我们参考下图，应该能够更简单的理解桶排序：

【十大经典排序算法】：桶排序示意图

看了示意图，然后我们就很容易理解了，整个排序流程分为几步：

1. 取最大值最小值
2. 定义桶
3. 将待排序的数分别放入桶中
4. 对每个桶分别排序
5. 依次将数从桶中取出

注意

从上图我们也能看出，当所有数字都被分配到同一个桶中，排序速度最慢，而所有数字均匀分配到不同的桶中，排序速度最快；所以，为了让桶排序更加高效，我们需要

1. 在空间允许的情况下尽量加大桶数目
2. 尽量保证数据均匀分配到桶中

所以，上图示意图中的数组并不是非常适合于桶排序

java代码

public class BucketSort implements IArraySort {

    // 这里引用插入排序，用于对每个桶内元素进行单独排序
    purivate static final InsertSort insertSort = new InsertSort();

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return bucketSort(arr, 5);
    }

    private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
        if (arr.length == 0) {
            return arr;
        }

        int minValue = arr[0];
        int maxValue = arr[0];
        for (int value : arr) {
            if (value < minValue) {
                minValue = value;
            } else if (value > maxValue) {
                maxValue = value;
            }
        }

        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];

        // 利用映射函数将数据分配到各个桶中
        for (int i = 0; i < arr.length; i++) {
            int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
            buckets[index] = arrAppend(buckets[index], arr[i]);
        }

        int arrIndex = 0;
        for (int[] bucket : buckets) {
            if (bucket.length <= 0) {
                continue;
            }
            // 对每个桶进行排序，这里使用了插入排序
            bucket = insertSort.sort(bucket);
            for (int value : bucket) {
                arr[arrIndex++] = value;
            }
        }
        return arr;
    }

    /**
    * 自动扩容，并保存数据
    *
    * @param arr
    * @param value
    */
    private int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}