介绍

Fisher–Yates shuffle 算法是一个用来将一个有限集合生成一个随机排列的算法（数组随机排序）。这个算法生成的随机排列是等概率的。同时这个算法非常高效。

原理

根据每次迭代次数可以用下面的表格，描述这个算法的执行过程：

动画：

See the Pen Fisher–Yates shuffle by Chuan shi (@haoyang) on CodePen.

实现

JavaScript

/**
 * The Fisher–Yates shuffle is an algorithm for generating a random permutation of a finite sequence—in plain terms, the algorithm shuffles the sequence.
 **/
const fisherYatesShuffle = (array) => {
  let maxLength = array.length
  let temp
  let idx

  // While there remain elements to shuffle...
  while (maxLength) {
    // Pick a remaining element...
    idx = Math.floor(Math.random() * maxLength--)

    // And swap it with the current element
    temp = array[maxLength]
    array[maxLength] = array[idx]
    array[idx] = temp
  }

  return array
}

参考

• Fisher–Yates shuffle - Wikipedia (opens new window)