JavaScript 開發(fā)中有時(shí)會(huì)遇到要將一個(gè)數(shù)組隨機(jī)排序(shuffle)的需求，一個(gè)常見的寫法是這樣：

function shuffle(arr) { 
 
   arr.sort(function () { 
 
      return Math.random() - 0.5; 
 
   }); 
 
} 

或者使用更簡(jiǎn)潔的 ES6 的寫法：

function shuffle(arr) { 
 
    arr.sort(() => Math.random() - 0.5); 
 
} 

我也曾經(jīng)經(jīng)常使用這種寫法，不久前才意識(shí)到，這種寫法是有問(wèn)題的，它并不能真正地隨機(jī)打亂數(shù)組。

問(wèn)題

看下面的代碼，我們生成一個(gè)長(zhǎng)度為 10 的數(shù)組['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']，使用上面的方法將數(shù)組亂序，執(zhí)行多次后，會(huì)發(fā)現(xiàn)每個(gè)元素仍然有很大機(jī)率在它原來(lái)的位置附近出現(xiàn)。

let n = 10000; 
 
let count = (new Array(10)).fill(0); 
 
  
 
for (let i = 0; i < n; i ++) { 
 
    let arr = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']; 
 
    arr.sort(() => Math.random() - 0.5); 
 
    count[arr.indexOf('a')]++; 
 
} 
 
  
 
console.log(count); 

在 Node.JS 6 中執(zhí)行，輸出[ 2891, 2928, 1927, 1125, 579, 270, 151, 76, 34, 19 ](帶有一定隨機(jī)性，每次結(jié)果都不同，但大致分布應(yīng)該一致)，即進(jìn)行 10000 次排序后，字母'a'(數(shù)組中的***個(gè)元素)有約 2891 次出現(xiàn)在***個(gè)位置、2928 次出現(xiàn)在第二個(gè)位置，與之對(duì)應(yīng)的只有 19 次出現(xiàn)在***一個(gè)位置。如果把這個(gè)分布繪制成圖像，會(huì)是下面這樣：

類似地，我們可以算出字母'f'(數(shù)組中的第六個(gè)元素)在各個(gè)位置出現(xiàn)的分布為[ 312, 294, 579, 1012, 1781, 2232, 1758, 1129, 586, 317 ]，圖像如下：

如果排序真的是隨機(jī)的，那么每個(gè)元素在每個(gè)位置出現(xiàn)的概率都應(yīng)該一樣，實(shí)驗(yàn)結(jié)果各個(gè)位置的數(shù)字應(yīng)該很接近，而不應(yīng)像現(xiàn)在這樣明顯地集中在原來(lái)位置附近。因此，我們可以認(rèn)為，使用形如arr.sort(() => Math.random() - 0.5)這樣的方法得到的并不是真正的隨機(jī)排序。

另外，需要注意的是上面的分布僅適用于數(shù)組長(zhǎng)度不超過(guò) 10 的情況，如果數(shù)組更長(zhǎng)，比如長(zhǎng)度為 11，則會(huì)是另一種分布。比如：

let a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k']; // 長(zhǎng)度為11 
 
let n = 10000; 
 
let count = (new Array(a.length)).fill(0); 
 
  
 
for (let i = 0; i < n; i ++) { 
 
    let arr = [].concat(a); 
 
    arr.sort(() => Math.random() - 0.5); 
 
    count[arr.indexOf('a')]++; 
 
} 
 
  
 
console.log(count); 

在 Node.JS 6 中執(zhí)行，結(jié)果為[ 785, 819, 594, 679, 941, 1067, 932, 697, 624, 986, 1876 ]，其中***個(gè)元素'a'的分布圖如下：

sort_03

分布不同的原因是 v8 引擎中針對(duì)短數(shù)組和長(zhǎng)數(shù)組使用了不同的排序方法(下面會(huì)講)。可以看到，兩種算法的結(jié)果雖然不同，但都明顯不夠均勻。

國(guó)外有人寫了一個(gè)Shuffle算法可視化的頁(yè)面，在上面可以更直觀地看到使用arr.sort(() => Math.random() - 0.5)的確是很不隨機(jī)的。

探索

看了一下ECMAScript中關(guān)于Array.prototype.sort(comparefn)的標(biāo)準(zhǔn)，其中并沒(méi)有規(guī)定具體的實(shí)現(xiàn)算法，但是提到一點(diǎn)：

Calling comparefn(a,b) always returns the same value v when given a specific pair of values a and b as its two arguments.

也就是說(shuō)，對(duì)同一組a、b的值，comparefn(a, b)需要總是返回相同的值。而上面的() => Math.random() - 0.5(即(a, b) => Math.random() - 0.5)顯然不滿足這個(gè)條件。

翻看v8引擎數(shù)組部分的源碼，注意到它出于對(duì)性能的考慮，對(duì)短數(shù)組使用的是插入排序，對(duì)長(zhǎng)數(shù)組則使用了快速排序，至此，也就能理解為什么() => Math.random() - 0.5并不能真正隨機(jī)打亂數(shù)組排序了。(有一個(gè)沒(méi)明白的地方：源碼中說(shuō)的是對(duì)長(zhǎng)度小于等于 22 的使用插入排序，大于 22 的使用快排，但實(shí)際測(cè)試結(jié)果顯示分界長(zhǎng)度是 10。)

解決方案

知道問(wèn)題所在，解決方案也就比較簡(jiǎn)單了。

方案一

既然(a, b) => Math.random() - 0.5的問(wèn)題是不能保證針對(duì)同一組a、b每次返回的值相同，那么我們不妨將數(shù)組元素改造一下，比如將每個(gè)元素i改造為：

let new_i = { 
 
    v: i, 
 
    r: Math.random() 
 
}; 

即將它改造為一個(gè)對(duì)象，原來(lái)的值存儲(chǔ)在鍵v中，同時(shí)給它增加一個(gè)鍵r，值為一個(gè)隨機(jī)數(shù)，然后排序時(shí)比較這個(gè)隨機(jī)數(shù)：

arr.sort((a, b) => a.r - b.r); 

完整代碼如下：

function shuffle(arr) { 
 
    let new_arr = arr.map(i => ({v: i, r: Math.random()})); 
 
    new_arr.sort((a, b) => a.r - b.r); 
 
    arr.splice(0, arr.length, ...new_arr.map(i => i.v)); 
 
} 
 
  
 
let a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']; 
 
let n = 10000; 
 
let count = (new Array(a.length)).fill(0); 
 
  
 
for (let i = 0; i < n; i ++) { 
 
    shuffle(a); 
 
    count[a.indexOf('a')]++; 
 
} 
 
  
 
console.log(count); 

一次執(zhí)行結(jié)果為：[ 1023, 991, 1007, 967, 990, 1032, 968, 1061, 990, 971 ]。多次驗(yàn)證，同時(shí)在這兒查看shuffle(arr)函數(shù)結(jié)果的可視化分布，可以看到，這個(gè)方法可以認(rèn)為足夠隨機(jī)了。

方案二(Fisher–Yates shuffle)

需要注意的是，上面的方法雖然滿足隨機(jī)性要求了，但在性能上并不是很好，需要遍歷幾次數(shù)組，還要對(duì)數(shù)組進(jìn)行splice等操作。

考察Lodash 庫(kù)中的 shuffle 算法，注意到它使用的實(shí)際上是Fisher–Yates 洗牌算法，這個(gè)算法由 Ronald Fisher 和 Frank Yates 于 1938 年提出，然后在 1964 年由 Richard Durstenfeld 改編為適用于電腦編程的版本。用偽代碼描述如下：

-- To shuffle an array a of n elements (indices 0..n-1): 
 
for i from n−1 downto 1 do 
 
     j ← random integer such that 0 ≤ j ≤ i 
 
     exchange a[j] and a[i] 

一個(gè)實(shí)現(xiàn)如下(ES6)：

function shuffle(arr) { 
 
    let i = arr.length; 
 
    while (i) { 
 
        let j = Math.floor(Math.random() * i--); 
 
        [arr[j], arr[i]] = [arr[i], arr[j]]; 
 
    } 
 
} 

或者對(duì)應(yīng)的 ES5 版本：

function shuffle(arr) { 
 
  var i = arr.length, t, j; 
 
  while (i) { 
 
    j = Math.floor(Math.random() * i--); 
 
    t = arr[i]; 
 
    arr[i] = arr[j]; 
 
    arr[j] = t; 
 
  } 
 
} 

小結(jié)

如果要將數(shù)組隨機(jī)排序，千萬(wàn)不要再用(a, b) => Math.random() - 0.5這樣的方法。目前而言，F(xiàn)isher–Yates shuffle 算法應(yīng)該是***的選擇。