关于javascript:随机打乱数组及Fisher–Yates-shuffle算法详解

介绍几种随机打乱数组的办法，及其利弊。

一、Array.prototype.sort 排序

留神一下，sort() 办法会扭转原数组，看代码：

// ES6 写法
function randomShuffle(arr) {return arr.sort(() => Math.random() - 0.5)
}

// ES5 写法
function randomShuffle(arr) {var compareFn = function () {return Math.random() - 0.5
  }
  return arr.sort(compareFn)
}

但实际上 这种办法并不能真正的随机打乱数组。在屡次执行后，每个元素有很大几率还在它原来的地位左近呈现。可看下这篇文章：罕用的 sort 打乱数组办法真的有用？

二、Fisher–Yates shuffle 经典洗牌算法

这种算法思维，目前有两种稍有不同的实现形式，这里我把它们都算入 Fisher–Yates shuffle。别离是 Fisher–Yates shuffle 和 Knuth-Durstenfeld Shuffle。

驰名的 Lodash 库的办法 _.shuffle() 也是应用了该算法。

1. Fisher–Yates shuffle（Fisher and Yates’ original method）

由 Ronald Fisher 和 Frank Yates 提出的 Fisher–Yates shuffle 算法思维，艰深来说是这样的：

假如有一个长度为 N 的数组

1. 从第 1 个到残余的未删除项（蕴含）之间抉择一个随机数 k。
2. 从残余的元素中将第 k 个元素删除并取出，放到新数组中。
3. 反复第 1、2 步直到所有元素都被删除。
4. 最终将新数组返回

实现

function shuffle(arr) {
  var random
  var newArr = []

  while (arr.length) {random = Math.floor(Math.random() * arr.length)
    newArr.push(arr[random])
    arr.splice(random, 1)
  }

  return newArr
}

举例

假如咱们有 1 ~ 8 的数字

表格每列别离示意：范畴、随机数（被移除数的地位）、残余未删除的数、已随机排列的数。

当初，咱们从 1 ~ 8 中随机抉择一个数，失去随机数 k 为 3，而后在 Scratch 上删除第 k 个数字（即数字 3），并将其放到 Result 中：

当初咱们从 1 ~ 7 抉择第二个随机数 k 为 4，而后在 Scratch 上删除第 k 个数字（即数字 5），并将其放到 Result 中：

当初咱们从 1 ~ 6 抉择下一个随机数，而后从 1 ~ 5 抉择依此类推，总是反复上述过程：

2. Knuth-Durstenfeld Shuffle（The modern algorithm）

Richard Durstenfeld 于 1964 年推出了古代版本的 Fisher–Yates shuffle，并由 Donald E. Knuth 在 The Art of Computer Programming 以“Algorithm P (Shuffling)”进行了推广。Durstenfeld 所形容的算法与 Fisher 和 Yates 所给出的算法有很小的差别，但意义重大。

-- To shuffle an array a of n elements (indices 0..n-1):  
for i from n−1 downto 1 do  // 数组从 n-1 到 0 循环执行 n 次
  j ← random integer such that 0 ≤ j ≤ i  // 生成一个 0 到 n-1 之间的随机索引
  exchange a[j] and a[i] // 将替换之后残余的序列中最初一个元素与随机选取的元素替换

Durstenfeld 的解决方案是将“删除 ”的数字移至数组 开端 ，即 将每个被删除数字与最初一个未删除的数字进行替换。

实现

// ES6 写法
function shuffle(arr) {
  let i = arr.length

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

  return arr
}


// ES5 写法
function shuffle(arr) {
  var i = arr.length
  var j
  var t

  while (--i) {j = Math.floor(Math.random() * i)
    t = arr[i]
    arr[i] = arr[j]
    arr[j] = t
  }
  
  return arr
}

Knuth-Durstenfeld Shuffle 将算法的工夫复杂度升高到 O(n)，而 Fisher–Yates shuffle 的工夫复杂度为 O(n2)。后者在计算机实现过程中，将破费不必要的工夫来计算每次残余的数字（能够了解成数组长度）。

举例

同样，假如咱们有 1 ~ 8 的数字

表格每列别离示意：范畴、以后随机数（即随机交互的地位）、残余未替换的数、已随机排列的数。

咱们从 1 ~ 8 中随机抉择一个数，失去随机数 k 为 6，而后替换 Scratch 中的第 6 和第 8 个数字：

接着，从 1 ~ 7 中随机抉择一个数，失去随机数 k 为 2，而后替换 Scratch 中的第 2 和第 7 个数字：

持续，下一个随机数是 1 ~ 6，失去的随机数恰好是 6，这意味着咱们将列表中的第 6 个数字保留下来（通过下面的替换，当初是 8），而后移到下一个步。同样，咱们以雷同的形式进行操作，直到实现排列：

因而，后果是 7 5 4 3 1 8 2 6。

三、总结

若要实现随机打乱数组的需要，不要再应用 arr.sort(() => Math.random() - 0.5) 这种办法了。目前用得较多的是 Knuth-Durstenfeld Shuffle 算法。

四、参考

• 罕用的 sort 打乱数组办法真的有用？
• Fisher–Yates Shuffle 可视化
• Fisher–Yates shuffle wiki
• 洗牌算法（shuffle）的 js 实现