洗牌算法实现数组乱序

Question

关于 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，里面通过动画生动地介绍了洗牌算法地高效乱序实现方式。