数组随机排序

Fisher–Yates shuffle

数组随机排序 原理基于： Fisher–Yates shuffle (洗牌算法)

数组随机排序作用

举个最简单的例子，玩扑克牌，需要洗牌，把原本按顺序排列的牌打乱，重新排序

经典的算法实现

• 1. 给定一组待混排的有限序列 P
• 2. 新初始化一个空的序列 Q
• 3. 从 P 中随机选取一个元素
• 4. 将该元素放到序列 Q 的最后面,并从序列 P 中移除该元素 重复 3-4 的步骤,直到序列 P 中元素全部选取到了序列 Q 中,得到的序列 Q 即为一组 P 的混排序列

考虑到数组只有一层，所以用个 concat 进行浅拷贝一样，让我们方法修改后不影响原数组

Array.prototype.shuffle = function() {
  const arr = [].concat(this)
  const res = []
  for (let i = arr.length; i > 0; i--) {
    const index = Math.floor(Math.random() * i)
    res.push(arr[index])
    arr.splice(index, 1)
  }
  return res
}

流行的算法实现

经典的算法貌似满足我们大多数的需求了,但是现代人精益求精,又提出了现代算法
与经典算法不同的是,现代算法在操作过程中 不需要借助一个新的序列 而可以直接在当前序列中完成
算法步骤大致相同:

• 1. 给定一组待混排的有限序列 P
• 2. 从 P 中随机选取一个未混排的元素
• 3. 将该元素与序列 P 的最后一个未混排的元素交换 重复 2-3 的步骤,直到序列 P 中元素全部混排过

Array.prototype.shuffle = function() {
  const arr = [].concat(this)
  for (let i = arr.length; i > 0; i--) {
    const idx = Math.floor(Math.random() * i)
    if (idx !== i - 1) {
      const tmp = arr[idx]
      arr[idx] = arr[i - 1]
      arr[i - 1] = tmp

      // 上面的是老写法，还需要一个临时变量
      // es6支持的解构赋值，省去了这部分的麻烦
      // ;[arr[idx], arr[i - 1]] = [arr[i - 1], arr[idx]]
    }
  }
  return arr
}

最后附上 Lodash 库中 Shuffle 实现

Lodash 库中的实现方式其实就是现代算法的实现方式

import copyArray from './.internal/copyArray.js'

function shuffle(array) {
  const length = array == null ? 0 : array.length
  if (!length) {
    return []
  }
  let index = -1
  const lastIndex = length - 1
  const result = copyArray(array)
  while (++index < length) {
    const rand = index + Math.floor(Math.random() * (lastIndex - index + 1))
    const value = result[rand]
    result[rand] = result[index]
    result[index] = value
  }
  return result
}

export default shuffle