Fisher–Yates shuffle - 《Google V8 底层机制和原理》

shuffle 改进
shuffle现代算法

Fisher–Yates shuffle 算法之所以有这个命名,当然是由Fisher和Yates这两个人的发明的,一开始只是用来人工混排一组数字序列,原始算法的步骤非常容易理解.
比如为了产生数字1-N之间的一组混排,可按如下步骤:

写下从 1 到 N 的数字
取一个从 1 到剩下的数字（包括1）的随机数 k
得到第 k 个数字（这个数字还没有被取出），把它写在独立的一个列表的最后一位
重复第 2 步，直到所有的数字都被取出
第 3 步写出的这个序列，现在就是原始数字的随机排列

前面说过,原始算法是用来人工混排的,如果计算机严格按照此步骤执行,第三步加上第四部的”重复”动作决定了最坏情况下,原始方法的时间复杂度是O(n);

shuffle 改进

对于稍微懂点编程思想的人来说,原始的算法很容易改进,因为我们不会在第三步之后对原始的列表进行改动。下面我们稍微改进一下:

给定一组待混排的有限序列P
新初始化一个空的序列Q
从P中随机选取一个元素
将该元素放到序列Q的最后面,并从序列P中移除该元素

重复3-4的步骤,直到序列P中元素全部选取到了序列Q中,得到的序列Q即为一组P的混排序列

javascript实现经典shuffle算法代码：

function shuffle(arr) {
  if(!Array.isArray(arr) && arr.length) {
    return []
  }
  const res = []
  for(let i = arr.length; i > 0; i --) {
    const index = Math.floor(Math.random() * i)
    res.push(arr[index])
    arr.splice(index, 1)
  }
  return res;
}

shuffle现代算法

经典的算法貌似满足大多数的需求了,但是为精益求精的态度又提出了现代算法, 与经典算法不同的是,现代算法在操作过程中不需要借助一个新的序列 , 而可以直接在当前序列中完成.算法步骤大致相同:

给定一组待混排的有限序列P
从P中随机选取一个未混排的元素
将该元素与序列P的最后一个未混排的元素交换

重复2-3的步骤,直到序列P中元素全部混排过

javascript实现经典shuffle算法代码：

function shuffle (arr) {
  if(!Array.isArray(arr) && arr.length) {
    return []
  }
  for (let i = arr.length; i > 0; i--){
    const index=  Math.floor(Math.random() * i)
    if(index !== (i-1)) {
      const tmp = arr[index];
      arr[index] = arr[i-1]
      arr[i-1] = tmp
    }
  }
  return arr
}

比较经典算法和现代算法,可以发现,前者是返回新的数组,后者会改变原数组 underscore/Lodash库中Shuffle就是现代算法的实现,不同的是其交换的元素是从数组首位开始的,并且返回一个新数组。

underscore库shuffle算法代码：

  _.shuffle = function(obj) {
    var set = obj && obj.length === +obj.length ? obj : _.values(obj);
    var length = set.length;
    var shuffled = Array(length);
    for (var index = 0, rand; index < length; index++) {
      rand = _.random(0, index);
      if (rand !== index) shuffled[index] = shuffled[rand];
      shuffled[rand] = set[index];
    }
    return shuffled;
  };