需要把陣列元素打亂順序時,網路上流傳最廣的寫法是拿 sort 配上一個隨機比較函數。它確實能跑,但並不是好方案。
var list = [1, 2, 3, 4, 5, 6, 7, 8, 9];
list = list.sort(function() { return Math.random() - 0.5; });
Print(list); // 例如:4,3,1,2,9,5,6,7,8
排序演算法的前提是「比較結果必須一致」——同一對元素比較兩次應該得到相同答案。而 Math.random() - 0.5 每次都回傳不同的值,等於給排序演算法餵入自相矛盾的資訊。後果是打亂的程度並不均勻:某些排列出現的機率會明顯高於其他,而且不同瀏覽器引擎的排序實作不同,結果也不一致。
從尾端往前掃,每一輪在「剩餘範圍」內隨機挑一個位置與當前位置交換:
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;
}
var list = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(shuffle(list));
這個演算法能保證 n 個元素的每一種排列出現機率完全相同,時間複雜度 O(n),也只跟原陣列交換,不需要額外的比較邏輯。打牌、抽獎、隨機抽樣題組等情境都應該用它,而不是 sort。