《算法导论》ʚ读书笔记&浅析ɞ 第八章 - 桶排序(包含js版代码实现)_js算法导论

什么是桶排序

桶排序可以看做是计数排序的一种升级方式
桶排序是指将一组数据按照一定的区间进行分类，可以简单理解就是看第一位数子 把他们分类。

然后在每个桶内进行排序 此时你可以使用任意的排序方法
桶排序对数据有限制 如果不是同等位数的 数字的话 桶排序就没有太大的意义了

算法过程

1. 将数据分类
2. 组内排序
3. 组合

算法实现

function BucketSort(arr) {
    let l = arr.length
    if (l <= 1) return arr
    let max = Math.max.apply(null, arr)
    let result = []
    let buckets = new Array(l).fill([])
    for (let i = 0; i < l; i++) {
        let BucketIndex = parseInt(arr[i].toString()[0])
        buckets[BucketIndex].length == 0 ? buckets[BucketIndex] = [arr[i]] : buckets[BucketIndex].push(arr[i])
    }
    buckets.forEach(e => {
        QuickSort(e, 0, e.length - 1)
        result = result.concat(e)
    })
    return result
}

module.exports = BucketSort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18