某天深夜队伟，我翻開了群聊記錄穴吹，發(fā)現(xiàn)每個(gè)歪歪斜斜的氣泡上都寫著“隨機(jī)“兩個(gè)字。我橫豎睡不著嗜侮，仔細(xì)看了半夜港令，才從字縫里看出字來，滿屏都寫著四個(gè)字是“洗牌算法”锈颗！
-- 魯迅

20200814截屏.jpg

解決思路

要實(shí)現(xiàn)隨機(jī)發(fā)送n個(gè)的需求顷霹，可以先將數(shù)據(jù)使用洗牌算法隨機(jī)重排，然后選用連續(xù)的n個(gè)數(shù)據(jù)即可击吱。
洗牌算法有三種淋淀，對(duì)應(yīng)三種思想--“抽牌”、“換牌”姨拥、“插牌”绅喉，后者都是對(duì)前者進(jìn)行了不同程度上的優(yōu)化，我們來看看這幾種洗牌是怎么樣實(shí)現(xiàn)的叫乌，適用于哪些場景柴罐。

一、抽牌法 （ Fisher-Yates Shuffle）

• 思路：從牌堆隨機(jī)抽出憨奸，放入新牌堆革屠。

// js實(shí)現(xiàn)寫法
const shuffle = arr => {
    let copy = [], n = arr.length;
    while(n) {
        let j = parseInt(Math.random() * n--);
        copy.push(...arr.splice(j,1));
    }
    return copy;
};

• 復(fù)雜度：時(shí)間復(fù)雜度O(n2)（循環(huán)+刪除移動(dòng)）、空間復(fù)雜度O(n)。
• 圖示：
  
  洗牌算法之取牌法.png

二似芝、換牌法 （Knuth-Durstenfeld Shuffle）

• 思路：對(duì)上述抽牌法做了改進(jìn)那婉，無需將牌放入新牌堆，而是與現(xiàn)有牌堆中未抽中的最后一張進(jìn)行交換位置即可党瓮。

// js實(shí)現(xiàn)寫法
const shuffle = arr => {
    for(let i=arr.length-1; i>0; i--){
        let j = parseInt(Math.random()*(i+1));
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
    return arr;
};

• 復(fù)雜度：時(shí)間復(fù)雜度O(n)详炬、空間復(fù)雜度O(1)，原地重排
• 適用條件：知道數(shù)組長度寞奸、非動(dòng)態(tài)增加的數(shù)組（因?yàn)槭菑暮笸皰撸?/li>
• 圖示：
  
  洗牌算法之換牌法.png

三呛谜、 插牌法（Inside-Out Algorithm）

• 思路：對(duì)以上的換牌法進(jìn)行了優(yōu)化，從前往后掃枪萄，隨機(jī)插入到新牌堆中去隐岛。

// js實(shí)現(xiàn)寫法
const shuffle = arr => {
    let copy = [], i = 0;
    while(!!arr[i]) {
        let j = parseInt(Math.random()*(copy.length+1));
        if(!!copy[j]) {
            let tmp = copy[j];
            copy[j] = arr[i];
            copy.push(tmp);
        }else {
            copy[j] = arr[i];
        }       
        i++;
    }
    return copy;
};

• 復(fù)雜度：時(shí)間復(fù)雜度O(n)、空間復(fù)雜度O(n)
• 適用條件：不知長度瓷翻，或者動(dòng)態(tài)增加的數(shù)組也適用聚凹。
• 圖示：（可以很明顯看出，該算法不會(huì)改變?cè)瓟?shù)組）
  
  洗牌算法之插牌法.png

后話：剛發(fā)現(xiàn)Python直接就有shuffle()函數(shù)齐帚，我只想說Python牛逼...

更新：

IMG_20200822_235433.jpg

本文完