摘要：看完部分的源碼，首先迫不及待想跟大家分享的正是本文主題數(shù)組亂序。這是一道經(jīng)典的前端面試題，給你一個(gè)數(shù)組，將其打亂，返回新的數(shù)組，即為數(shù)組亂序，也稱(chēng)為洗牌問(wèn)題。關(guān)于數(shù)組亂序，正確的解法應(yīng)該是，復(fù)雜度。

終于可以開(kāi)始 Collection Functions 部分了。

可能有的童鞋是第一次看樓主的系列文章，這里再做下簡(jiǎn)單的介紹。樓主在閱讀 underscore.js 源碼的時(shí)候，學(xué)到了很多，同時(shí)覺(jué)得有些知識(shí)點(diǎn)可以獨(dú)立出來(lái)，寫(xiě)成文章與大家分享，而本文正是其中之一（完整的系列請(qǐng)猛戳 https://github.com/hanzichi/underscore-analysis）。之前樓主已經(jīng)和大家分享了 Object 和 Array 的擴(kuò)展方法中一些有意思的知識(shí)點(diǎn)，今天開(kāi)始解讀 Collection 部分。

看完 Collection Functions 部分的源碼，首先迫不及待想跟大家分享的正是本文主題 —— 數(shù)組亂序。這是一道經(jīng)典的前端面試題，給你一個(gè)數(shù)組，將其打亂，返回新的數(shù)組，即為數(shù)組亂序，也稱(chēng)為洗牌問(wèn)題。

一個(gè)好的方案需要具備兩個(gè)條件，一是正確性，毋庸置疑，這是必須的，二是高效性，在確保正確的前提下，如何將復(fù)雜度降到最小，是我們需要思考的。

幾年前樓主還真碰到過(guò)洗牌問(wèn)題，還真的是 "洗牌"。當(dāng)時(shí)是用 cocos2d-js（那時(shí)還叫 cocos2d-html5）做牌類(lèi)游戲，發(fā)牌前毫無(wú)疑問(wèn)需要洗牌。

當(dāng)時(shí)我是這樣做的。每次 random 一個(gè)下標(biāo)，看看這個(gè)元素有沒(méi)有被選過(guò)，如果被選過(guò)了，繼續(xù) random，如果沒(méi)有，將其標(biāo)記，然后存入返回?cái)?shù)組，直到所有元素都被標(biāo)記了。后來(lái)經(jīng)同事指導(dǎo)，每次選中后，可以直接從數(shù)組中刪除，無(wú)需標(biāo)記了，于是得到下面的代碼。

function shuffle(a) {
  var b = [];

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

  return b;
}

這個(gè)解法的正確性應(yīng)該是沒(méi)有問(wèn)題的（有興趣的可以自己去證明下）。我們假設(shè)數(shù)組的元素為 0 - 10，對(duì)其亂序 N 次，那么每個(gè)位置上的結(jié)果加起來(lái)的平均值理論上應(yīng)該接近 (0 + 10) / 2 = 5，且 N 越大，越接近 5。為了能有個(gè)直觀的視覺(jué)感受，我們假設(shè)亂序 1w 次，并且將結(jié)果做成了圖表，猛戳 http://hanzichi.github.io/test-case/shuffle/splice/ 查看，結(jié)果還是很樂(lè)觀的。

驗(yàn)證了正確性，還要關(guān)心一下它的復(fù)雜度。由于程序中用了 splice，如果把 splice 的復(fù)雜度看成是 O(n)，那么整個(gè)程序的復(fù)雜度是 O(n^2)。

另一個(gè)為人津津樂(lè)道的方法是 "巧妙應(yīng)用" JavaScript 中的 Math.random() 函數(shù)。

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

同樣是 [0, 1, 2 ... 10] 作為初始值，同樣跑了 1w 組 case，結(jié)果請(qǐng)猛戳 http://hanzichi.github.io/test-case/shuffle/Math.random/。

看平均值的圖表，很明顯可以看到曲線浮動(dòng)，而且多次刷新，折現(xiàn)的大致走向一致，平均值更是在 5 上下 0.4 的區(qū)間浮動(dòng)。如果我們將 [0, 1, 2 .. 9] 作為初始數(shù)組，可以看到更加明顯不符預(yù)期的結(jié)果（有興趣的可以自己去試下）。究其原因，要追究 JavaScript 引擎對(duì)于 Math.random() 的實(shí)現(xiàn)原理，這里就不展開(kāi)了（其實(shí)是我也不知道）。因?yàn)?ECMAScript 并沒(méi)有規(guī)定 JavaScript 引擎對(duì)于 Math.random() 應(yīng)該實(shí)現(xiàn)的方式，所以我猜想不同瀏覽器經(jīng)過(guò)這樣的亂序后，結(jié)果也不一樣。

什么時(shí)候可以用這種方法亂序呢？"非正式" 場(chǎng)合，一些手寫(xiě) DEMO 需要亂序的場(chǎng)合，這不失為一種 clever solution。

但是這種解法不但不正確，而且 sort 的復(fù)雜度，平均下來(lái)應(yīng)該是 O(nlogn)，跟我們接下來(lái)要說(shuō)的正解還是有不少差距的。

關(guān)于數(shù)組亂序，正確的解法應(yīng)該是 Fisher–Yates Shuffle，復(fù)雜度 O(n)。

其實(shí)它的思想非常的簡(jiǎn)單，遍歷數(shù)組元素，將其與之前的任意元素交換。因?yàn)楸闅v有從前向后和從后往前兩種方式，所以該算法大致也有兩個(gè)版本的實(shí)現(xià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 中采用從前往后遍歷元素的方式，實(shí)現(xiàn)如下：

// 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;
};

將其解耦分離出來(lái)，如下：

function shuffle(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;
}

跟前面一樣，做了下數(shù)據(jù)圖表，猛戳 http://hanzichi.github.io/test-case/shuffle/Fisher-Yates/。

關(guān)于證明，引用自月影老師的文章：

隨機(jī)性的數(shù)學(xué)歸納法證明

對(duì) n 個(gè)數(shù)進(jìn)行隨機(jī)：

首先我們考慮 n = 2 的情況，根據(jù)算法，顯然有 1/2 的概率兩個(gè)數(shù)交換，有 1/2 的概率兩個(gè)數(shù)不交換，因此對(duì) n = 2 的情況，元素出現(xiàn)在每個(gè)位置的概率都是 1/2，滿(mǎn)足隨機(jī)性要求。

假設(shè)有 i 個(gè)數(shù)， i >= 2 時(shí)，算法隨機(jī)性符合要求，即每個(gè)數(shù)出現(xiàn)在 i 個(gè)位置上每個(gè)位置的概率都是 1/i。

對(duì)于 i + 1 個(gè)數(shù)，按照我們的算法，在第一次循環(huán)時(shí)，每個(gè)數(shù)都有 1/(i+1) 的概率被交換到最末尾，所以每個(gè)元素出現(xiàn)在最末一位的概率都是 1/(i+1) 。而每個(gè)數(shù)也都有 i/(i+1) 的概率不被交換到最末尾，如果不被交換，從第二次循環(huán)開(kāi)始還原成 i 個(gè)數(shù)隨機(jī)，根據(jù) 2. 的假設(shè)，它們出現(xiàn)在 i 個(gè)位置的概率是 1/i。因此每個(gè)數(shù)出現(xiàn)在前 i 位任意一位的概率是 (i/(i+1)) * (1/i) = 1/(i+1)，也是 1/(i+1)。

綜合 1. 2. 3. 得出，對(duì)于任意 n >= 2，經(jīng)過(guò)這個(gè)算法，每個(gè)元素出現(xiàn)在 n 個(gè)位置任意一個(gè)位置的概率都是 1/n。

關(guān)于數(shù)組亂序，如果面試中被問(wèn)到，能說(shuō)出 "Fisher–Yates Shuffle"，并且能基本說(shuō)出原理（你也看到了，其實(shí)代碼非常的簡(jiǎn)單），那么基本應(yīng)該沒(méi)有問(wèn)題了；如果能更進(jìn)一步，將其證明呈上（甚至一些面試官都可能一時(shí)證明不了），那么就牛逼了。千萬(wàn)不能只會(huì)用 Math.random() 投機(jī)取巧！

Read More：

數(shù)組的完全隨機(jī)排列（推薦）

Fisher–Yates Shuffle（推薦）

如何測(cè)試洗牌程序

How to randomize (shuffle) a JavaScript array?

Code for Shuffling an Array