前言
終于可以開始 Collection Functions 部分了。
可能有的童鞋是第一次看樓主的系列文章把兔，這里再做下簡單的介紹葛家。樓主在閱讀 underscore.js 源碼的時候喷好，學到了很多，同時覺得有些知識點可以獨立出來缅刽，寫成文章與大家分享啊掏，而本文正是其中之一（完整的系列請猛戳 https://github.com/hanzichi/underscore-analysis）。之前樓主已經(jīng)和大家分享了 Object 和 Array 的擴展方法中一些有意思的知識點拷恨，今天開始解讀 Collection 部分脖律。
看完 Collection Functions 部分的源碼，首先迫不及待想跟大家分享的正是本文主題 —— 數(shù)組亂序腕侄。這是一道經(jīng)典的前端面試題小泉，給你一個數(shù)組，將其打亂冕杠，返回新的數(shù)組微姊，即為數(shù)組亂序，也稱為洗牌問題分预。
一個好的方案需要具備兩個條件兢交，一是正確性，毋庸置疑笼痹，這是必須的配喳，二是高效性，在確保正確的前提下凳干，如何將復雜度降到最小晴裹，是我們需要思考的。
splice
幾年前樓主還真碰到過洗牌問題救赐，還真的是 "洗牌"涧团。當時是用 cocos2d-js（那時還叫 cocos2d-html5）做牌類游戲，發(fā)牌前毫無疑問需要洗牌。
當時我是這樣做的。每次 random 一個下標，看看這個元素有沒有被選過柴钻，如果被選過了渣刷，繼續(xù) random，如果沒有，將其標記，然后存入返回數(shù)組，直到所有元素都被標記了惠毁。后來經(jīng)同事指導，每次選中后崎页，可以直接從數(shù)組中刪除鞠绰，無需標記了，于是得到下面的代碼飒焦。
function shuffle(a) {
var b = [];
while (a.length) {
var index = ~~(Math.random() * a.length);
b.push(a[index]);
a.splice(index, 1);
}
return b;
}
這個解法的正確性應該是沒有問題的（有興趣的可以自己去證明下）蜈膨。我們假設數(shù)組的元素為 0 - 10，對其亂序 N 次牺荠，那么每個位置上的結果加起來的平均值理論上應該接近 (0 + 10) / 2 = 5翁巍，且 N 越大，越接近 5休雌。為了能有個直觀的視覺感受灶壶，我們假設亂序 1w 次，并且將結果做成了圖表杈曲，猛戳 http://hanzichi.github.io/test-case/shuffle/splice/ 查看驰凛，結果還是很樂觀的。
驗證了正確性担扑，還要關心一下它的復雜度恰响。由于程序中用了 splice，如果把 splice 的復雜度看成是 O(n)涌献，那么整個程序的復雜度是 O(n^2)胚宦。
Math.random()
另一個為人津津樂道的方法是 "巧妙應用" 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枢劝，結果請猛戳 http://hanzichi.github.io/test-case/shuffle/Math.random/。
看平均值的圖表卜壕，很明顯可以看到曲線浮動呈野，而且多次刷新，折現(xiàn)的大致走向一致印叁，平均值更是在 5 上下 0.4 的區(qū)間浮動。如果我們將 [0, 1, 2 .. 9] 作為初始數(shù)組，可以看到更加明顯不符預期的結果（有興趣的可以自己去試下）轮蜕。究其原因昨悼，要追究 JavaScript 引擎對于 Math.random() 的實現(xiàn)原理，這里就不展開了（其實是我也不知道）跃洛。因為 ECMAScript 并沒有規(guī)定 JavaScript 引擎對于 Math.random() 應該實現(xiàn)的方式率触，所以我猜想不同瀏覽器經(jīng)過這樣的亂序后，結果也不一樣汇竭。
什么時候可以用這種方法亂序呢葱蝗？"非正式" 場合，一些手寫 DEMO 需要亂序的場合细燎，這不失為一種 clever solution两曼。
但是這種解法不但不正確，而且 sort 的復雜度玻驻，平均下來應該是 O(nlogn)悼凑，跟我們接下來要說的正解還是有不少差距的。
Fisher–Yates Shuffle
關于數(shù)組亂序璧瞬，正確的解法應該是 Fisher–Yates Shuffle户辫，復雜度 O(n)。
其實它的思想非常的簡單嗤锉，遍歷數(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 中采用從前往后遍歷元素的方式，實現(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;
};
將其解耦分離出來酷誓，如下：
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/盐数。
關于證明棒拂，引用自月影老師的文章：
隨機性的數(shù)學歸納法證明
對 n 個數(shù)進行隨機：
首先我們考慮 n = 2 的情況，根據(jù)算法玫氢，顯然有 1/2 的概率兩個數(shù)交換帚屉，有 1/2 的概率兩個數(shù)不交換，因此對 n = 2 的情況漾峡，元素出現(xiàn)在每個位置的概率都是 1/2攻旦，滿足隨機性要求。
假設有 i 個數(shù)生逸， i >= 2 時牢屋，算法隨機性符合要求且预，即每個數(shù)出現(xiàn)在 i 個位置上每個位置的概率都是 1/i。
對于 i + 1 個數(shù)烙无，按照我們的算法锋谐，在第一次循環(huán)時，每個數(shù)都有 1/(i+1) 的概率被交換到最末尾截酷，所以每個元素出現(xiàn)在最末一位的概率都是 1/(i+1) 涮拗。而每個數(shù)也都有 i/(i+1) 的概率不被交換到最末尾，如果不被交換迂苛，從第二次循環(huán)開始還原成 i 個數(shù)隨機三热，根據(jù) 2. 的假設，它們出現(xiàn)在 i 個位置的概率是 1/i三幻。因此每個數(shù)出現(xiàn)在前 i 位任意一位的概率是 (i/(i+1)) * (1/i) = 1/(i+1)就漾，也是 1/(i+1)。
綜合 1. 2. 3. 得出赌髓，對于任意 n >= 2从藤，經(jīng)過這個算法，每個元素出現(xiàn)在 n 個位置任意一個位置的概率都是 1/n锁蠕。
小結
關于數(shù)組亂序夷野，如果面試中被問到，能說出 "Fisher–Yates Shuffle"荣倾，并且能基本說出原理（你也看到了悯搔，其實代碼非常的簡單），那么基本應該沒有問題了舌仍；如果能更進一步妒貌，將其證明呈上（甚至一些面試官都可能一時證明不了），那么就牛逼了铸豁。千萬不能只會用 Math.random() 投機取巧灌曙！
Read More：
