陣列亂序就是把元素的排列順序打亂。最常見的寫法是給 sort 傳一個隨機比較函式:
arr.sort(function(a, b){ return Math.random() > .5 ? -1 : 1; });
這種寫法很直觀,但效率不佳。實測打亂 10000 個元素,在 Firefox 下約耗時 35ms。
if (!Array.prototype.shuffle) {
Array.prototype.shuffle = function() {
for (var j, x, i = this.length; i; j = parseInt(Math.random() * i), x = this[--i], this[i] = this[j], this[j] = x);
return this;
};
}
arr.shuffle();
同樣打亂 10000 個元素,這個版本只需 7、8 毫秒。把元素增加到 100000 來測試,sort 版本耗時 500ms 以上,shuffle 版本約 40ms,差距接近十倍。
效能面:sort 需要呼叫比較函式 O(n log n) 次,而每次比較都重新呼叫一次 Math.random()。更糟的是,比較函式必須是「一致的」——同樣的兩個元素每次比較都該回傳相同結果。隨機比較函式違反了這個契約,會讓排序演算法的分區邏輯失效,某些引擎甚至可能進入極端分支。
正確性面:即使不管效能,隨機比較函式產生的排列分布也是不均勻的。某些排列出現的機率會明顯高於其他,這是數學上可證的結果。
原始程式裡的 for(var j, x, i = this.length; i; j = parseInt(Math.random() * i), x = this[--i], this[i] = this[j], this[j] = x); 看起來很詭異——只有 for(...),後面直接接分號,沒有大括號。這是合法的 JavaScript:單一陳述式的位置放一個空陳述式(就是那個分號),而所有工作都在 for 的第三段(更新運算式)裡完成,用逗號運算子把四個動作串起來。
它其實在做 Fisher-Yates 洗牌演算法:從尾端往前,每次取一個 0 到 i 之間的隨機索引 j,把 this[i] 與 this[j] 互換。
function shuffle(arr) {
for (var i = arr.length - 1; i > 0; i--) {
var j = Math.floor(Math.random() * (i + 1)); // 0 到 i(含)
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
return arr;
}
用解構賦值會更短:
function shuffle(arr) {
for (let i = arr.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[arr[i], arr[j]] = [arr[j], arr[i]];
}
return arr;
}
注意隨機範圍是 i + 1 而非 i。原版用 parseInt(Math.random() * i) 搭配 --i,因為 i 先被遞減,所以範圍剛好正確;自己改寫時若不留意這個細節,會讓最後一個元素永遠沒有機會被選中,分佈就不均勻了。
這個函式會改動原陣列。若需要保留原陣列,先複製:shuffle(arr.slice())。
擴充 Array.prototype 也可能與其他函式庫衝突,特別是它們也用 for...in 遍歷陣列時。匯出成獨立函式是更安全的選擇。
若需要可重現的結果(例如測試),把 Math.random 換成帶种子的偽隨機數生成器(PRNG)即可,Fisher-Yates 演算法本身與隨機來源無關。