I Don't Know JS

Appearance

Return to top
On this page

04. 随机打乱算法

随机比较函数排序（不推荐）

js
const randomSort = (arr) => {
  arr.sort((a, b) => Math.random() - 0.5)
}
1
2
3

WARNING

不推荐这种方法，由于 ES 规定 sort(cmp) 接受的比较函数 cmp(a, b) 规定对于 a, b，要求结果是确定的，例如某一次比较 cmp(a,b) 结果为正数，下次又比较 cmp(a,b) 结果为负数，这样就会导致排序结果不稳定，不符合规范，那么这种打乱算法就不可靠了。

改进的随机比较函数排序

js
function shuffle(array) {
  const tempArray = array.map(value => ({ value, i: Math.random() }))
  tempArray.sort((a, b) => a.i - b.i)
  array.forEach((_, i) => {
    array[i] = tempArray[i].value
  })
}
1
2
3
4
5
6
7

基本思路是：既然导致上述问题出现的原因是每次 cmp(a, b) 的结果不能确定，那我们就令它的比较结果确定下来。我们可以设 a,b 为一个对象，附带一个属性 i，提前给 a,b 绑定好 i 属性，比较的时候比较提前确定下来的 i 属性即可。

更易于理解的方法：

js
function shuffle(array) {
  let random = array.map(Math.random)
  array.sort(function (a, b) {
    return random[a] - random[b]
  })
}
1
2
3
4
5
6

洗牌算法（Fisher-Yates shuffle）

js
function shuffle(arr) {
  let len = arr.length;
  while (len) {
    let randomIndex = Math.floor(Math.random() * len--);
    [arr[randomIndex], arr[len]] = [arr[len], arr[randomIndex]];
  }
  return arr;
}
1
2
3
4
5
6
7
8

基本思路：基本原理是将数组分为两部分，打乱的部分和未打乱的部分，每次都从未打乱的部分里面随机取出一个加入到打乱的部分里面。