我怎么又去研究算法了呢?自己不是根正苗红CS专业,基础差,亡羊补牢,填充数据结构方面的空白,学习过程遇到有趣的算法就记录下来。
常见算法,多为 c c++ python 所描述,为方便,尝试转成日常所用javascript 才疏学浅,如有写的不当之处,不吝赐教。🙏🙏🙏🙏

桶排序

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function bucketSort (arr) {
// 假设我们排序的范围为0-10 那么我们准备11个桶来放这些数字
let buckets = new Array(11).fill(0)
let newArr = []
// 装桶
arr.forEach(val => { buckets[val]++ })
buckets.forEach((val, index) => {
for (let i = 1; i <= val; i++) {
newArr.push(index)
}
})
return newArr
}
console.log(bucketSort([5, 3, 5, 2, 8]))
console.log(bucketSort([1, 3, 9, 8, 7, 2]))
console.log(bucketSort([3, 5, 2, 7, 9, 2, 5]))

图解:

理解:

桶排序 (Bucket sort)或所谓的箱排序的原理是将数组分到有限数量的桶子里,然后对每个桶子再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序),最后将各个桶中的数据有序的合并起来。

  1. 根据数列最大值设置桶数量
  2. 把数据放到对应的桶里
  3. 循环输出不为空桶里面的数据,计数多少输出多少次

桶排序动画演示: Bucket Sort Visualization
特点:

  1. 桶排序是稳定的
  2. 桶排序是常见排序里最快的一种,比快排还要快…大多数情况下
  3. 桶排序非常快,但是同时也非常耗空间,基本上是最耗空间的一种排序算法

参考资料

  1. 常见排序算法 - 桶排序 (Bucket Sort)