介绍几种随机打乱数组的办法，及其利弊。
一、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 个到残余的未删除项（蕴含）之间抉择一个随机数 k。
- 从残余的元素中将第 k 个元素删除并取出，放到新数组中。
- 反复第 1、2 步直到所有元素都被删除。
- 最终将新数组返回
实现
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 的数字
表格每列别离示意：范畴、随机数（被移除数的地位）、残余未删除的数、已随机排列的数。
| Range | Roll | Scratch | Result |
|---|---|---|---|
| 1 2 3 4 5 6 7 8 |
当初，咱们从 1 ~ 8 中随机抉择一个数，失去随机数 k 为 3，而后在 Scratch 上删除第 k 个数字（即数字 3），并将其放到 Result 中：
| Range | Roll | Scratch | Result |
|---|---|---|---|
| 1 - 8 | 3 | 1 2 | 3 |
当初咱们从 1 ~ 7 抉择第二个随机数 k 为 4，而后在 Scratch 上删除第 k 个数字（即数字 5），并将其放到 Result 中：
| Range | Roll | Scratch | Result |
|---|---|---|---|
| 1 - 7 | 4 | 1 2 | 3 5 |
当初咱们从 1 ~ 6 抉择下一个随机数，而后从 1 ~ 5 抉择依此类推，总是反复上述过程：
| Range | Roll | Scratch | Result |
|---|---|---|---|
| 1–6 | 5 | 1 2 | 3 5 7 |
| 1–5 | 3 | 1 2 | 3 5 7 4 |
| 1–4 | 4 | 1 2 | 3 5 7 4 8 |
| 1–3 | 1 | 3 5 7 4 8 1 | |
| 1–2 | 2 | 3 5 7 4 8 1 6 | |
| 3 5 7 4 8 1 6 2 |
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 的数字
表格每列别离示意：范畴、以后随机数（即随机交互的地位）、残余未替换的数、已随机排列的数。
| Range | Roll | Scratch | Result |
|---|---|---|---|
| 1 2 3 4 5 6 7 8 |
咱们从 1 ~ 8 中随机抉择一个数，失去随机数 k 为 6，而后替换 Scratch 中的第 6 和第 8 个数字：
| Range | Roll | Scratch | Result |
|---|---|---|---|
| 1 - 8 | 6 | 1 2 3 4 5 8 7 | 6 |
接着，从 1 ~ 7 中随机抉择一个数，失去随机数 k 为 2，而后替换 Scratch 中的第 2 和第 7 个数字：
| Range | Roll | Scratch | Result |
|---|---|---|---|
| 1 - 7 | 6 | 1 7 3 4 5 8 | 2 6 |
持续，下一个随机数是1 ~ 6，失去的随机数恰好是 6，这意味着咱们将列表中的第 6 个数字保留下来（通过下面的替换，当初是 8），而后移到下一个步。同样，咱们以雷同的形式进行操作，直到实现排列：
| Range | Roll | Scratch | Result |
|---|---|---|---|
| 1 - 6 | 6 | 1 7 3 4 5 | 8 2 6 |
| 1 - 5 | 1 | 5 7 3 4 | 1 8 2 6 |
| 1 - 4 | 3 | 5 7 4 | 3 1 8 2 6 |
| 1 - 3 | 3 | 5 7 | 4 3 1 8 2 6 |
| 1 - 2 | 1 | 7 | 5 4 3 1 8 2 6 |
因而，后果是 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 实现