桶排序

[wl05]

桶排序思想：

1. 将元素放入有序的桶中。
2. 对每个不是空的桶里面的元素进行排序。
3. 合并桶最后得到排序好的数列。

function insertionSort(array) {
    for (let i = 1; i < array.length; i++) {
        let j = i
        let target = array[j]
        while (j > 0 && array[j - 1] > target) {
            array[j] = array[j - 1]
            j--
        }
        array[j] = target
    }
    return array
}
function bucketSort(array, size = 10) {
    let min = array[0];
    let max = array[0];
    for (let i = 1; i < array.length; i++) { // {4}
        if (array[i] < min) {
            min = array[i];
        } else if (array[i] > max) {
            max = array[i];
        }
    }
    const count = Math.floor((max - min) / size) + 1
    const buckets = []
    for (let i = 0; i < count; i++) {
        buckets.push([])
    }
    array.forEach(item => {
        const num = Math.floor((item - min) / size)
        buckets[num].push(item)
    })
    const result = []
    buckets.forEach(bucket => {
        result.push(...insertionSort(bucket))
    })

    return result
}
console.log(bucketSort([2, 1, 3, 100000000000000000000], 10000000000000000))