IT博客汇 | 随机排列一个数组 · 看不见我的美

随机排列一个数组 · 看不见我的美 · 是你瞎了眼

馬腊咯稽发表于 2019-05-22 00:00:00

Array.prototype.sort()

sort 方法不能实现随机排序的原因是：当对一个数组进行 n 次排序后，这 n 个数组的第 x 项的平均数并不是无限接近于原数组所有项的平均数。

1
2
3
4
5
6
7
8
9


const arr = [1, 7, 0, 5, 6, 4, 2, 9, 3, 8];
// [1, 7, 0, 5, 6, 4, 2, 9, 3, 8]
console.log(arr.slice().sort((a, b) => 0)); // 保持不变
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
console.log(arr.slice().sort((a, b) => a - b)); // 升序
// [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
console.log(arr.concat().sort((a, b) => b - a)); // 降序
// [3, 6, 5, 2, 9, 7, 1, 0, 4, 8]
console.log(arr.concat().sort((a, b) => 0.5 - Math.random())); // 伪随机

经典洗牌算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


function randomList(initArr) {
 let length = initArr.length,
 tempArr = [], // 保存随机下标
 resultArr = []; // 保存结果
 while (length) {
 // 随机下标 [0, initArr.length] 的整数
 let randomIndex = Math.floor(Math.random() * initArr.length);
 // 防止随机下标重复
 if (!tempArr.includes(randomIndex)) {
 tempArr.push(randomIndex);
 resultArr[randomIndex] = initArr[length - 1];
 length--;
 }
 }
 return resultArr;
}
let arr = [1, 7, 0, 5, 6, 4, 2, 9, 3, 8];
console.log(randomList(arr));

Fisher–Yates

1
2
3
4
5
6
7
8
9


function shuffleList(a) {
 for (let i = a.length; i; i--) {
 let j = Math.floor(Math.random() * i);
 [a[i - 1], a[j]] = [a[j], a[i - 1]];
 }
 return a;
}
let arr = [1, 7, 0, 5, 6, 4, 2, 9, 3, 8];
console.log(shuffleList(arr));

参考

JS 中随机排列数组顺序（经典洗牌算法）和数组的排序方法