桶排序

基本概念

桶排序是把数据按照规则放到不同的数组中，然后对数组中的数据排序，最终再将数组合并为一个数组。

实现原理

• 设置一个定值正整数作为桶的数量，我们需要把数据分别放到这些桶中，一般默认桶数量为，向下取整((最大值-最小值)/数组长度) +1；
• 遍历数组，根据某种算法，将元素放到对应的桶中，算法一般为，桶位置 = 向下取整（（元素值-最小值）/ 原数组长度；
• 对各个桶中的元素进行排序，此时可以借用任意你喜欢的排序方法，原生、选择排序、计数排序等等；
• 在数组中排除空桶；
• 将所用带有数据的桶进行合并；

关键参数

• 确定每个桶的容量bucketSize，默认桶容量为数组的长度，当然也可以自定义，比如桶容量为5，为10
• 确定桶数量，桶数量=向下取整((最大值-最小值 )/ 桶容量) + 1，bucketCount = Math.floot((max-min) / bucketSize) + 1
• 确定哪个元素放到哪个桶：位置=向下取整((元素值-最小值) / 桶容量)，pos = Math.floor((val-min) / bucketSize)

代码实现

/**
 * 桶排序
 * @param {[]number} arr 
 */
function bucketSort(arr) {
    // 1.确定桶容量
    const bucketSize = arr.length

    // 2.确定最大值和最小值
    let min = arr[0]
    let max = arr[0]
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < min) {
            min = arr[i]
        } else if (arr[i] > max) {
            max = arr[i]
        }
    }
    // 也可以直接用
    // let min = Math.min(...arr)
    // let max = Math.max(...arr)

    // 3.确定桶数量，初始化桶数组
    const bucketCount = Math.floor((max - min) / bucketSize) + 1
    const buckets = new Array(bucketCount).fill(0).map(() => []) // 初始化桶数组

    // 4.确定哪个元素分配到哪个桶
    for (let i = 0; i < arr.length; i++) {
        // 确定位置
        const pos = Math.floor((arr[i] - min) / bucketSize)
        buckets[pos].push(arr[i])
    }
    // console.log(buckets)

    // 5.对每个桶进行排序
    for (let i = 0; i < buckets.length; i++) {
        buckets[i].sort((a, b) => a - b)
    }
    // console.log(buckets)

    // 6.合并桶
    let res = []
    for (let i = 0; i < buckets.length; i++) {
        res = res.concat(buckets[i])
    }

    return res
}

console.log(bucketSort([-3, 4, 5, 2, 3, 1, 102, 100, 108]))