08 洗牌算法实现数组乱序

关于 JavaScript 数组乱序的方法有多种实现方式,或者借助一些第三方开源工具库如 loadsh 也可以轻松实现,然而要做到数组足够的无规律乱序也非易予,还是有一些要点需要考虑。

sort 方法

最简单的便是使用 sort 函数,代码如下:

const shuffle = arr => {
arr.sort(() => Math.random() > 0.5)
return arr
}

在一般场景中以上代码实现便可满足功能需求,但仅是使用 sort 函数的乱序方式并不完美,出于 v8 引擎的底层原因,它对长短数组采用不同的排序方式,并不能真正随机打乱数组排序,简而言之就是最后得到的数组不能足够乱。

由于 v8 引擎出于对性能的考虑,sort 函数对短数组(长度小于 10)使用的是插入排序,对长数组则使用了快速排序。其实不管用什么排序方法,大多数排序算法的时间复杂度介于 O(n) 到 O(n2) 之间,元素之间的比较次数通常情况下要远小于 n(n-1)/2,也就意味着有一些元素之间根本就没机会相比较(也就没有了随机交换的可能),这使 sort 随机排序的算法自然也不能真正随机。通俗的说,其实我们使用 array.sort 进行乱序,理想的方案或者说纯乱序的方案是:数组中每两个元素都要进行比较,这个比较有 50% 的交换位置概率。如此一来,总共比较次数一定为 n(n-1)。而在 sort 排序算法中,大多数情况都不会满足这样的条件。因而当然不是完全随机的结果了。

Fisher–Yates Shuffle 洗牌算法

Fisher–Yates Shuffle 洗牌算法是目前业界最著名的数组乱序算法之一,并且能够使数组足够乱,实现如下:

const shuffle = arr => {
let i = arr.length
let j
while (i) {
j = Math.floor(Math.random() * i--)
;[arr[i], arr[j]] = [arr[j], arr[i]]
}
return arr
}

关于更多洗牌算法的细节详见 Fisher–Yates Shuffle,里面通过动画生动地介绍了洗牌算法地高效乱序实现方式。