前言

• 在網(wǎng)上看到一個(gè)簡單但很經(jīng)典的題目，就是給一個(gè)數(shù)組，要求將數(shù)組元素的排序隨機(jī)打亂，實(shí)現(xiàn)的方法有很多，最受推崇的方法還是Fisher–Yates shuffle洗牌算法。下面會(huì)依次介紹三個(gè)方法，均能完成功能，各種區(qū)別

一個(gè)不太好的實(shí)現(xiàn)

• 這是我看完題目后馬上想到的一個(gè)方法，每次從原數(shù)組中隨機(jī)取出一項(xiàng)，放進(jìn)結(jié)果數(shù)組，直到原數(shù)組內(nèi)的元素全部取出。這個(gè)方法很明顯的一個(gè)缺陷就是：需要另外再聲明一個(gè)數(shù)組變量，也算占用了額外的內(nèi)存地址。

function getRandom (arr) {
  let dp = [...arr]
  let result = []
  while (dp.length > 0) {
    let randomIndex = Math.floor(Math.random() * (dp.length))
    result.push(dp.splice(randomIndex, 1)[0])
  }
  return result
}

一個(gè)抖機(jī)靈的實(shí)現(xiàn)

• 還有一個(gè)抖機(jī)靈的實(shí)現(xiàn)方法，利用數(shù)組的sort排序方法。每次調(diào)用Math.random生成的隨機(jī)數(shù)去和0.5作比較，來實(shí)現(xiàn)元素位置的重新排序。缺點(diǎn)在于相比其他兩個(gè)方法，運(yùn)算時(shí)間更長(待驗(yàn)證)。

function getRandom (arr) {
    let dp = [...arr]
    return dp.sort(() => Math.random() < .5)
}

Fisher–Yates shuffle

• 具體內(nèi)容可以去看它的維基百科，我這里直接說下他的實(shí)現(xiàn)原理：
  • 倒序循環(huán)這個(gè)數(shù)組
  • 取 范圍從 1到n 的隨機(jī)數(shù) k
  • k 與 n 做交換
  • 直到循環(huán)到數(shù)組的首個(gè)元素
• 相比第一個(gè)方法，就不需要定義額外的變量，每次對元素進(jìn)行兩兩位置的交換，時(shí)間復(fù)雜度同樣為O(n)，下面是具體代碼：

function shuffle (arr) {
  let res = [...arr]
  for (let i = arr.length - 1; i > 0; i--) {
    let randomIndex = Math.floor(Math.random() * (i + 1))
    let randomItem = res[randomIndex]
    res[randomIndex] = res[i]
    res[i] = randomItem
  }
  return res
}