洗牌数组
重要性：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 算法要好得多，没有“排序”开销。