桶排序

概要

桶排序是计数排序的优化版，原理都是一样的：分治法+空间换时间。
将数组进行分组，减少排序的数量，再对子数组进行排序，最后合并即可得到结果。

效果图

解法

tip

对桶内数字的排序，本文采用的是桶排序递归。其实它的本质是退化到计数排序。

function bucketSort(arr, bucketSize = 10){
    // bucketSize 每个桶可以存放的数字区间(0, 9]

    if(arr.length <= 1){
        return arr;
    }
    
    let maxValue = arr[0];
    let minValue = arr[0];
    let result = [];

    // 取出数组的最大值, 最小值
    arr.forEach(num => {
        maxValue = num > maxValue ? num : maxValue;
        minValue = num > minValue ? minValue : num;
    });

    // 初始化桶的数量
    const bucketCount = Math.floor((maxValue - minValue)/bucketSize) + 1; // 桶的数量
    // 初始化桶的容器
    // 注意这里的js语法，不能直接fill([])，因为生成的二维下标数组，是同一个地址
    const buckets = new Array(bucketCount).fill(0).map(() => []);

    // 将数字按照映射的规则，放入桶中
    arr.forEach(num => {
        const bucketIndex = Math.floor((num - minValue)/bucketSize);
        buckets[bucketIndex].push(num);
    });

    // 遍历每个桶内存储的数字
    buckets.forEach(store => {
        // 桶内只有1个数字或者空桶，或者都是重复数字，则直接合并到结果中
        if(store.length <= 1 || bucketSize == 1){
            result = result.concat(store);
            return;
        }

        // 递归，将桶内的数字，再进行一次划分到不同的桶中
        const subSize = Math.floor(bucketSize/2); // 减少桶内的数字区间，但必须是最少为1
        const tmp = bucketSort(store, subSize <= 1 ? 1: subSize);
        result = result.concat(tmp);
    });

    return result;
}

参考

• JAVA十大排序算法之桶排序详解