一、随机化算法：不只是“碰运气”

说实话，很多同学一听到“随机化算法”，第一反应就是“这不就是靠运气吗？”
嗯，我刚开始学的时候也这么想。直到我在一个广告推荐系统里，遇到了海量数据需要抽样——那时候我才意识到，随机化算法其实是一门非常严谨的数学艺术。

今天咱们聊两个最经典的随机化算法：洗牌算法和蓄水池抽样。
说白了，一个解决“怎么把数组打乱得足够随机”，另一个解决“数据流太大，我只想抽几个样本，怎么保证公平”。

1.1 洗牌算法：Fisher-Yates 才是正统

先问个问题：给你一个数组，你怎么把它随机打乱？
我见过不少人直接写 Math.random() 排序，或者每次随机取一个元素放到新数组里。这些方法其实都有问题。

真正靠谱的是 Fisher-Yates 洗牌算法，也叫 Knuth 洗牌。
它的核心思想很简单：从后往前遍历，每次从当前位置之前（包括自己）随机选一个元素，然后交换。

// 经典 Fisher-Yates 洗牌
function shuffle(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

为什么从后往前？
我个人习惯从后往前写，因为这样只需要一次遍历，而且不需要额外空间。你想想看，如果从前往后，每次选中的位置可能会被后面覆盖，逻辑就乱了。

1.2 蓄水池抽样：数据流里的公平抽样

洗牌算法解决的是“已知全部数据”的情况。
但如果你面对的是一个数据流——比如实时日志、无限长的用户点击序列——你根本不知道总共有多少条数据，怎么办？

这时候就要用 蓄水池抽样（Reservoir Sampling） 了。

它的思路很巧妙：

• 先保留前 k 个元素作为样本
• 从第 k+1 个元素开始，以 k / i 的概率决定是否替换掉样本中的一个
• 被替换的元素也是随机选的

// 蓄水池抽样：从数据流中随机抽取 k 个元素
function reservoirSampling(stream, k) {
  const reservoir = [];
  let i = 0;

  for (const item of stream) {
    if (i < k) {
      reservoir.push(item);
    } else {
      const j = Math.floor(Math.random() * (i + 1));
      if (j < k) {
        reservoir[j] = item;
      }
    }
    i++;
  }

  return reservoir;
}

为什么这样能保证公平？
数学证明我就不展开了，你只需要记住：每个元素被选中的概率都是 k/n，其中 n 是总数据量。即使 n 未知，这个性质依然成立。

1.3 经典例题：打乱数组 & 随机数索引

光讲理论不过瘾，咱们直接上 LeetCode 原题。

例题1：打乱数组（LeetCode 384）

题目要求你实现一个类，支持 reset() 恢复原数组，shuffle() 返回随机打乱后的数组。

class Solution {
  constructor(nums) {
    this.original = [...nums];
    this.array = nums;
  }

  reset() {
    this.array = [...this.original];
    return this.array;
  }

  shuffle() {
    for (let i = this.array.length - 1; i > 0; i--) {
      const j = Math.floor(Math.random() * (i + 1));
      [this.array[i], this.array[j]] = [this.array[j], this.array[i]];
    }
    return this.array;
  }
}

这里有个小细节：reset() 要深拷贝原数组，否则你 shuffle 之后原数组也被改了。嗯，我刚开始写的时候就忘了这茬，debug 了半天。

例题2：随机数索引（LeetCode 398）

给定一个可能包含重复元素的数组，要求随机返回目标值的索引。每个索引被选中的概率要相等。

这题其实就是蓄水池抽样的变体——只不过我们只关心目标值出现的那些位置。

class Solution {
  constructor(nums) {
    this.nums = nums;
  }

  pick(target) {
    let count = 0;
    let result = -1;

    for (let i = 0; i < this.nums.length; i++) {
      if (this.nums[i] === target) {
        count++;
        // 以 1/count 的概率替换当前选中的索引
        if (Math.random() < 1 / count) {
          result = i;
        }
      }
    }

    return result;
  }
}

你看，代码只有几行，但背后的数学原理很扎实。
每次遇到目标值，都以 1/count 的概率替换掉之前选中的索引。这样每个索引被选中的概率都是 1/count。

1.4 知识体系总览

为了让你更直观地理解这两个算法的关系，我画了一张图：

1.5 总结与避坑

最后，我把自己这些年踩过的坑总结一下：

场景	推荐算法	常见错误
数组打乱	Fisher-Yates 洗牌	用 sort + random，概率不均匀
数据流抽样	蓄水池抽样	不知道数据总量就放弃抽样
重复元素随机索引	蓄水池抽样 (k=1)	先统计所有索引再随机选，浪费空间

其实这两个算法都不难，关键是要理解它们背后的“公平性”保证。
我当年面试字节跳动的时候，面试官就让我手写蓄水池抽样，还追问了数学证明。幸好我提前准备过，不然真可能翻车。

好了，这一章的内容就到这里。记住：随机化算法不是玄学，是数学。多写几遍代码，多推几遍概率，你就能真正掌握它。

---