数组乱序

[weisuoke]

原文

一道经典的面试题，给你一个数组，将其打乱，返回新的数组，即为数组乱序，也称洗牌问题？

Splice

当时我是这样做的。每次 random 一个下标，看看这个元素有没有被选过，如果被选过了，继续 random，如果没有，将其标记，然后存入返回数组，直到所有元素都被标记了。后来经同事指导，每次选中后，可以直接从数组中删除，无需标记了，于是得到下面的代码。

function shuffle(a) {
  var b = [];
  
  while (a.length) {
    var index = ~~(Math.random() * a.length);
    b.push(a[index]);
    a.splice(index, 1);
  }
  
  return b;
}

Math.random

另一个为人津津乐道的方法是 "巧妙应用" JavaScript 中的 Math.random() 函数。

function shuffle(a) {
  return a.concat().sort(function(a, b) {
    return Math.random() - 0.5;
  })
}

什么时候可以用这种方法乱序呢？"非正式" 场合，一些手写 DEMO 需要乱序的场合，这不失为一种 clever solution。

但是这种解法不但不正确，而且 sort 的复杂度，平均下来应该是 O(nlogn)，跟我们接下来要说的正解还是有不少差距的。

Fisher-Yates Shuffle

数组乱序, 正确的解法应该是Fisher-Yates Shuffle，复杂度O(n)

其实它的思想非常的简单，遍历数组元素，将其与之前的任意元素交换。因为遍历有从前向后往前两种方式，所以该算法也有两个版本的实现。

从后往前的版本：

function shuffle(array) {
  var _array = array.concat();
  
  for (var i = _array.length; i--;) {
    var j = Math.floor(Math.random() * (i + 1));
    var temp = _array[i];
    _array[i] = _array[j];
    _array[j] = temp;
  }
  
  return _array;
}

underscore 中采用从前往后遍历元素的方式，实现如下：

// Shuffle a collection, using the modern version of the
// [Fisher-Yates shuffle](http://en.wikipedia.org/wiki/Fisher–Yates_shuffle)
_.shuffle = function(obj) {
  var set = isArrayLike(obj) ? 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;
};

将其解耦分离出来，如下：

function shuffled(a) {
  var length = a.length;
  var shuffled = Array(length);
  
  for (var index = 0, rand; index < length; index++) {
    rand = ~~(Math.random() * (index + 1));
    if (rand !== index) {
      shuffled[index] = shuffled[rand]
    }
    shuffled[rand] = a[index];
  }
  
  return shuffled;
}

随机性的数学归纳法证明

对 n 个数进行随机：

1. 首先我们考虑 n = 2 的情况，根据算法，显然有 1/2 的概率两个数交换，有 1/2 的概率两个数不交换，因此对 n = 2 的情况，元素出现在每个位置的概率都是 1/2，满足随机性要求。
2. 假设有 i 个数， i >= 2 时，算法随机性符合要求，即每个数出现在 i 个位置上每个位置的概率都是 1/i。
3. 对于 i + 1 个数，按照我们的算法，在第一次循环时，每个数都有 1/(i+1) 的概率被交换到最末尾，所以每个元素出现在最末一位的概率都是 1/(i+1) 。而每个数也都有 i/(i+1) 的概率不被交换到最末尾，如果不被交换，从第二次循环开始还原成 i 个数随机，根据 2. 的假设，它们出现在 i 个位置的概率是 1/i。因此每个数出现在前 i 位任意一位的概率是 (i/(i+1)) * (1/i) = 1/(i+1)，也是 1/(i+1)。
4. 综合 1. 2. 3. 得出，对于任意 n >= 2，经过这个算法，每个元素出现在 n 个位置任意一个位置的概率都是 1/n

Read More：

• 数组的完全随机排列（推荐）
• Fisher–Yates Shuffle（推荐）
• 如何测试洗牌程序
• How to randomize (shuffle) a JavaScript array?
• Code for Shuffling an Array