sort 结合 Math.random
arr.sort(() => Math.random() - 0.5);
不是理想的乱序,
一些元素并没有机会相互比较,
array.sort方法排序底层
v8在处理sort方法时,使用了插入排序和快排两种方案。
当数组长度小于 10 时,使用插入排序;
当数组长度大于等于 10 时,使用快速排序。
两种排序的元素比较次数远小于n(n-1)
也就意味着有一些元素之间没机会相比较
理想的乱序
总共比较次数一定为n(n-1)。
Fisher–Yates
将数组从后向前遍历,
将当前元素与随机位置的元素进行交换
function shuffle(arr) {
let m = arr.length;
while (m > 1){
let index = Math.floor(Math.random() * m--);
[arr[m] , arr[index]] = [arr[index] , arr[m]];
}
return arr;
}
