震惊！某容同学竟在群里「在线发牌」？？

某天深夜，我翻开了群聊记录，发现每个歪歪斜斜的气泡上都写着“随机“两个字。我横竖睡不着，仔细看了半夜，才从字缝里看出字来，满屏都写着四个字是“洗牌算法”！
-- 鲁迅

20200814截屏.jpg

解决思路

要实现随机发送n个的需求，可以先将数据使用洗牌算法随机重排，然后选用连续的n个数据即可。
洗牌算法有三种，对应三种思想--“抽牌”、“换牌”、“插牌”，后者都是对前者进行了不同程度上的优化，我们来看看这几种洗牌是怎么样实现的，适用于哪些场景。

一、抽牌法 （ Fisher-Yates Shuffle）

• 思路：从牌堆随机抽出，放入新牌堆。

// js实现写法
const shuffle = arr => {
    let copy = [], n = arr.length;
    while(n) {
        let j = parseInt(Math.random() * n--);
        copy.push(...arr.splice(j,1));
    }
    return copy;
};

• 复杂度：时间复杂度O(n²)（循环+删除移动）、空间复杂度O(n)。
• 图示：
  洗牌算法之取牌法.png

二、换牌法 （Knuth-Durstenfeld Shuffle）

• 思路：对上述抽牌法做了改进，无需将牌放入新牌堆，而是与现有牌堆中未抽中的最后一张进行交换位置即可。

// js实现写法
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;
};

• 复杂度：时间复杂度O(n)、空间复杂度O(1)，原地重排
• 适用条件：知道数组长度、非动态增加的数组（因为是从后往前扫）
• 图示：
  洗牌算法之换牌法.png

三、 插牌法（Inside-Out Algorithm）

• 思路：对以上的换牌法进行了优化，从前往后扫，随机插入到新牌堆中去。

// js实现写法
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;
};

• 复杂度：时间复杂度O(n)、空间复杂度O(n)
• 适用条件：不知长度，或者动态增加的数组也适用。
• 图示：（可以很明显看出，该算法不会改变原数组）
  洗牌算法之插牌法.png

后话：刚发现Python直接就有shuffle()函数，我只想说Python牛逼...

---

更新：

IMG_20200822_235433.jpg
之后问了当时人，当事人给我讲了具体的场景，比较复杂，经过调研，给出了以下解决方案，请移步到蓄水池抽样-reservoir

本文完