洗牌是一個很形象的說法,本質上就是讓陣列裡的元素隨機重新排列。舉個例子,我們有一個長度為 9、元素值依序是 1 到 9 的陣列:

要做的事,就是把裡面的順序打亂:

維基百科的 Fisher–Yates shuffle 條目對這個算法有完整介紹,下面的實作便是依據同一套理論:
Array.prototype.shuffle = function() {
var input = this;
for (var i = input.length-1; i >=0; i--) {
var randomIndex = Math.floor(Math.random()*(i+1));
var itemAtIndex = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIndex;
}
return input;
}
var tempArray = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
tempArray.shuffle();
alert(tempArray);
這裡建立了一個 shuffle() 方法,並把它掛在 Array 的 prototype 上,於是任何陣列都能直接呼叫:
var tempArray = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]; tempArray.shuffle();
第一步,先鎖定陣列的最後一個元素:

接著決定隨機挑選的範圍——從第一個元素到剛剛選中的位置都算在內:

在這個範圍裡隨機挑一個,假設選中了 4:

然後交換最後一個元素與隨機選中元素的值:

這一步完成,等於處理好了最後一個位置。接著往前退一格,鎖定倒數第二個元素:

之所以由後往前處理,是因為這樣最容易界定隨機挑選的範圍。這次假設隨機選到 2:

交換倒數第一個與 2 號元素的值,倒數第二個位置也處理完了。再往前選倒數第三個元素,重複同樣的操作:

剩下的都是重複性工作,不再贅述。
Array.prototype.shuffle = function() {
var input = this;
for (var i = input.length-1; i >=0; i--) {
var randomIndex = Math.floor(Math.random()*(i+1));
var itemAtIndex = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIndex;
}
return input;
}
shuffle 掛在 Array 的 prototype 之下,方便陣列直接呼叫。函式內部的 this 指向的就是呼叫它的那個陣列,所以第一行用一個新變數把它接起來:
var input = this;
再看 for 迴圈做了什麼:
for (var i = input.length-1; i >=0; i--) {
var randomIndex = Math.floor(Math.random()*(i+1));
var itemAtIndex = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIndex;
}
這個迴圈會遍歷每個元素並逐一隨機交換。注意遍歷方向是從後往前,從 input.length-1 開始,一直到第一個元素為止,位置由變數 i 標示——也就是前面圖例中被選中的那個元素。
接著用兩行在指定範圍內挑一個隨機元素:
var randomIndex = Math.floor(Math.random()*(i+1)); var itemAtIndex = input[randomIndex];
randomIndex 存的是一個可當索引用的隨機數,用來取出隨機元素。要留意它的上限不是陣列長度,而是變數 i 的值——這正是「已處理過的尾段不再參與抽取」的關鍵。
索引確定後,用新變數保存該元素的值,再交換兩者:
var itemAtIndex = input[randomIndex]; input[randomIndex] = input[i]; input[i] = itemAtIndex;
第一行用暫存變數保存隨機元素的值;第二行把 input[i] 的值寫進隨機位置;第三行再把暫存的值寫回 input[i]。本質上就是交換兩個變數的值,並不難理解。

上圖是用 Highcharts 製作的隨機性測試圖表,以視覺化方式檢查這個洗牌算法夠不夠均勻,每次重新整理都會重算一次。
資料是這樣算出來的:先建立一個陣列(圖中用的是 [0, 1, 2 … 18, 19, 20]),套用本文的洗牌算法重新排序,記下每個位置的數值,重複 100000 次後,把同一索引位置上的數值全部加總。若算法夠均勻,各索引之間的總值應該相差不大。
實際計算結果:

以上就是 JS 洗牌算法在陣列隨機排序上的實作與驗證,希望對大家有幫助。