阅读 1366

手写算法并记住它:桶排序

对于经典算法,你是否也遇到这样的情形:学时觉得很清楚,可过阵子就忘了?

本系列文章就尝试解决这个问题。

研读那些排序算法,细品它们的名字,其实都很贴切。

比如桶排序,一提起“桶”,我就想到了垃圾分类。

桶排序就是先分类,即把数据放进相应的桶里,然后对每个桶进行局部排序,最后再把桶合并一下就行了。

上图演示了该算法的总体流程。分为三步,分类,排序和合并。

该算法的核心是如何分类,也就是,如何划分桶并把元素放进相应的桶里。

它的分类是按区间分类。图中元素最小值是1,最大值是9,因此所有元素位于属于区间【1,9】。假设桶(区间)的范围大小是3,那么就有3个桶,具体是:【1,3】、【4,6】、【7,9】。

用代码体现一下:

let array = [3, 8, 6, 1, 5, 7, 9, 2, 4]
let min = Math.min(...array)
let max = Math.max(...array)
let size = 3
let count = Math.floor((max - min) / size) + 1
let buckets = []
for (let i = 0; i < count; i++) {
  buckets.push([])
}
console.log(buckets) // [ [], [], [] ]
复制代码

总体来说代码比较简单,需要注意的是count的计算。

桶有了,接下来就是把每个元素归类。

for (let v of array) {
  let num = Math.floor((v - min) / size)
  buckets[num].push(v)
}
console.log(buckets) // [ [ 3, 1, 2 ], [ 6, 5, 4 ], [ 8, 7, 9 ] ]
复制代码

其中,num表示桶的序号,与count一样,也是通过偏移量来计算的。因为下标是从0开始的,因此这里没有再加1。

关键问题解决了,排序和合并就相对简单了。

排序用其他任一排序算法都可以,比如数据量不太大的时候,插入排序就比较适合。

因为区间本来就是有序的,合并时只需直接连接这些数组即可。

let result = []
for (bucket of buckets) {
  result.push(...insertionSort(bucket)) 
}
console.log(result) // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
复制代码

至此,桶排序原理和实现已经说完了。查看完整代码:codepen

其实还有优化的空间,比如min和max可以通过一次循环确定出来。另外一点是,我们知道插入排序的思想是把待排序元素插入到已排序序列里,因此可以在第一步分类时就直接插入就行。

这里总结一下,桶排序是分布式排序,适合处理大批量数据。需要额外空间,是外部排序。桶排序是否稳定,取决于第二步排序算法的选择。时间复杂度是线性级O(n),可以简单理解:桶的范围大小是人为指定的,它不随数据规模变化,如果数据相对均匀分布,那么桶的个数就是核心影响因子了。

桶排序,要做到能分分钟手写出来,是需要掌握其排序原理的。核心是如何划分区间和元素归类,一旦理解就容易写出来,不需要死记硬背的。

希望有所帮助,本文完。



本系列已经发表文章:

关注下面的标签,发现更多相似文章
评论