JavaScript随机打乱数组排序的几个方法

前言

• 在网上看到一个简单但很经典的题目，就是给一个数组，要求将数组元素的排序随机打乱，实现的方法有很多，最受推崇的方法还是Fisher–Yates shuffle洗牌算法。下面会依次介绍三个方法，均能完成功能，各种区别

一个不太好的实现

• 这是我看完题目后马上想到的一个方法，每次从原数组中随机取出一项，放进结果数组，直到原数组内的元素全部取出。这个方法很明显的一个缺陷就是：需要另外再声明一个数组变量，也算占用了额外的内存地址。

function getRandom (arr) {
  let dp = [...arr]
  let result = []
  while (dp.length > 0) {
    let randomIndex = Math.floor(Math.random() * (dp.length))
    result.push(dp.splice(randomIndex, 1)[0])
  }
  return result
}

一个抖机灵的实现

• 还有一个抖机灵的实现方法，利用数组的sort排序方法。每次调用Math.random生成的随机数去和0.5作比较，来实现元素位置的重新排序。缺点在于相比其他两个方法，运算时间更长(待验证)。

function getRandom (arr) {
    let dp = [...arr]
    return dp.sort(() => Math.random() < .5)
}

Fisher–Yates shuffle

• 具体内容可以去看它的维基百科，我这里直接说下他的实现原理：
  • 倒序循环这个数组
  • 取 范围从 1到n 的随机数 k
  • k 与 n 做交换
  • 直到循环到数组的首个元素
• 相比第一个方法，就不需要定义额外的变量，每次对元素进行两两位置的交换，时间复杂度同样为O(n)，下面是具体代码：

function shuffle (arr) {
  let res = [...arr]
  for (let i = arr.length - 1; i > 0; i--) {
    let randomIndex = Math.floor(Math.random() * (i + 1))
    let randomItem = res[randomIndex]
    res[randomIndex] = res[i]
    res[i] = randomItem
  }
  return res
}