【算法】桶排序算法的讲解和代码实践

思路

桶排序的思想同归并排序一样，也是基于分治法来加快排序的速度的。主要思想就是把整个数组按范围放到不同的桶中，各个桶各自进行排序，每个桶都排好序之后，整个数组的排序也就完成了。
思路：
1、确定桶的个数和每个桶的范围；
2、将数组分配到桶中；
3、桶内进行排序（可以继续使用桶排序，但一般会采用其他排序算法）；
4、从桶中取出排好序的数。

讲解

有数组如下：

image.png

加入分配5个桶，分别是[1, 20)、[20, 40)、[40，60)、[60，80)、[80，99)：

image.png

然后给数字进行入桶：

image.png

将桶中的数字进行排序：

image.png

将数字从桶中取出来即可：

image.png

实现

    @Test
    public void sortTest() {
        int[] nums = new int[]{2, 1, 31, 15, 28, 88, 46, 55, 57, 98};
        bucketSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    private void bucketSort(int[] nums) {
        if (nums.length < 2) {
            return;
        }
        // 找出最大值和最小值，决定分配几个桶
        int maxValue = nums[0];
        int minValue = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > maxValue) {
                maxValue = nums[i];
            }
            if (nums[i] < minValue) {
                minValue = nums[i];
            }
        }
        // 桶个数
        int bucketCount = (maxValue - minValue) / (nums.length * 2) + 1;
        // 如果桶个数小于两个，就没有必要分桶，直接排序即可
        if (bucketCount < 2) {
            Arrays.sort(nums);
            return;
        }
        // 桶间隔
        int gap = (maxValue + 1) / (bucketCount - 1);
        // 声明桶
        int[][] bucketArray = new int[bucketCount][0];
        // 遍历入桶
        for (int i = 0; i < nums.length; i++) {
            bucketArray[nums[i] / gap] = arrayAppend(bucketArray[nums[i] / gap], nums[i]);
        }
        // 桶内排序和取出
        int index = 0;
        for (int i = 0; i < bucketCount; i++) {
            // 每一个桶内进行排序，这里就简写了
            Arrays.sort(bucketArray[i]);
            // 取出放到结果数组
            for (int j = 0; j < bucketArray[i].length; j++) {
                nums[index++] = bucketArray[i][j];
            }
        }
    }

    private int[] arrayAppend(int[] array, int num) {
        int[] ints = Arrays.copyOf(array, array.length + 1);
        ints[ints.length - 1] = num;
        return ints;
    }

看下运行结果：

image.png