要把陣列洗牌,流傳最廣的寫法只有一行:
var arr = [];
for(var i = 0; i < 100; i++){
arr[i] = i;
}
arr.sort(function(){ return 0.5 - Math.random() })
var str = arr.join();
alert(str);
var arr = []; // 建立陣列,這是推薦寫法,而非 var arr = new Array();
for(var i = 0; i < 100; i++){ arr[i] = i; } // 循環賦值
關鍵在這一句:
arr.sort(function(){ return 0.5 - Math.random() })
sort 會反覆從陣列中挑兩個元素比較,依比較函式的回傳值決定要不要交換:回傳 0 表示兩者相等、位置不變;回傳小於 0 表示前者排前面;回傳大於 0 表示前者排後面。然後拿較大的那個跟下一個繼續比,這樣一輪輪進行下去。
而 0.5 - Math.random() 的結果必定落在 -0.5 到 0.5 之間,隨機為正或為負,於是每次比較都在「交換」與「不交換」之間擲硬幣,陣列看起來就被打亂了。
這段寫法雖然簡短、跑起來也夠快,卻不是均勻隨機。原因在於比較函式不是一致的:同一組元素在不同階段比較,可能得到不同結果,這違反了排序演算法對「比較結果必須可傳遞」的假設。實測會發現某些排列出現的機率明顯高於其他,元素越多偏差越明顯。
如果要真正均勻的洗牌,應該用 Fisher–Yates 演算法——從後往前,每一輪把當前元素與前面(含自己)隨機挑的一個位置交換:
function shuffle(arr){
for (var i = arr.length - 1; i > 0; i--) {
var j = Math.floor(Math.random() * (i + 1));
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
return arr;
}
它只跑一趟、時間複雜度 O(n),而且每一種排列出現的機率嚴格相等。若是需要密碼學强度的隨機(例如抽獎、產生 token),把 Math.random() 換成 crypto.getRandomValues(),因為前者並非安全隨機源。
所以那行經典寫法適合成不了大局的小場合;正式用途請用 Fisher–Yates。