洗牌陣列
重要性：3
撰寫函式 shuffle(array)，用來洗牌（隨機重新排列）陣列的元素。
執行 shuffle 多次可能會產生不同的元素順序。例如
let arr = [1, 2, 3];
shuffle(arr);
// arr = [3, 2, 1]
shuffle(arr);
// arr = [2, 1, 3]
shuffle(arr);
// arr = [3, 1, 2]
// ...所有元素順序應具有相同的機率。例如，[1,2,3] 可以重新排列為 [1,2,3] 或 [1,3,2] 或 [3,1,2] 等，每個案例的機率相同。
簡單的解決方案可能是
function shuffle(array) {
array.sort(() => Math.random() - 0.5);
}
let arr = [1, 2, 3];
shuffle(arr);
alert(arr);這在某種程度上是可行的，因為 Math.random() - 0.5 是可能為正或負的隨機數，因此排序功能會隨機重新排列元素。
但由於排序功能並非用於此方式，因此並非所有排列都具有相同的機率。
例如，考慮以下程式碼。它執行 shuffle 1000000 次，並計算所有可能結果的出現次數
function shuffle(array) {
array.sort(() => Math.random() - 0.5);
}
// counts of appearances for all possible permutations
let count = {
'123': 0,
'132': 0,
'213': 0,
'231': 0,
'321': 0,
'312': 0
};
for (let i = 0; i < 1000000; i++) {
let array = [1, 2, 3];
shuffle(array);
count[array.join('')]++;
}
// show counts of all possible permutations
for (let key in count) {
alert(`${key}: ${count[key]}`);
}範例結果（取決於 JS 引擎）
123: 250706
132: 124425
213: 249618
231: 124880
312: 125148
321: 125223我們可以清楚地看到偏差：123 和 213 出現的頻率遠高於其他數字。
程式碼的結果可能因 JavaScript 引擎而異，但我們已經可以看出這種方法不可靠。
為什麼它不起作用？一般來說，sort 是「黑盒子」：我們將陣列和比較函式放入其中，並期望陣列被排序。但由於比較的完全隨機性，黑盒子會發瘋，而它發瘋的方式取決於引擎之間不同的具體實作。
還有其他方法可以執行這項任務。例如，有一個很棒的演算法稱為 Fisher-Yates 洗牌。這個概念是按相反順序遍歷陣列，並將每個元素與它之前的隨機元素交換
function shuffle(array) {
for (let i = array.length - 1; i > 0; i--) {
let j = Math.floor(Math.random() * (i + 1)); // random index from 0 to i
// swap elements array[i] and array[j]
// we use "destructuring assignment" syntax to achieve that
// you'll find more details about that syntax in later chapters
// same can be written as:
// let t = array[i]; array[i] = array[j]; array[j] = t
[array[i], array[j]] = [array[j], array[i]];
}
}讓我們以相同的方式測試它
function shuffle(array) {
for (let i = array.length - 1; i > 0; i--) {
let j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
}
// counts of appearances for all possible permutations
let count = {
'123': 0,
'132': 0,
'213': 0,
'231': 0,
'321': 0,
'312': 0
};
for (let i = 0; i < 1000000; i++) {
let array = [1, 2, 3];
shuffle(array);
count[array.join('')]++;
}
// show counts of all possible permutations
for (let key in count) {
alert(`${key}: ${count[key]}`);
}範例輸出
123: 166693
132: 166647
213: 166628
231: 167517
312: 166199
321: 166316現在看起來不錯：所有排列都以相同的機率出現。
此外，在效能方面，Fisher-Yates 演算法好得多，沒有「排序」開銷。