[!info] related notes

• 所属 MOC: 算法面试题型 MOC
• 并列概念: quicksort, randomized-select
• 易混淆: .sort(() => Math.random() - 0.5) 是错误的洗牌方式
• 安全场景: crypto.getRandomValues

Fisher-Yates 洗牌算法

一句话定义

Fisher-Yates 洗牌算法通过从后往前遍历，每次在 [0, i] 范围内随机选一个位置交换，保证每个元素落在每个位置的概率严格相等。

核心机制

1. 从数组最后一个元素开始，向前遍历
2. 对于位置 i，在 [0, i] 范围内随机选一个索引 j
3. 交换 arr[i] 和 arr[j]
4. 重复直到遍历完所有元素

最小例子

function shuffle(arr) {
  const res = arr.slice(); // 不修改原数组
  for (let i = res.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [res[i], res[j]] = [res[j], res[i]];
  }
  return res;
}

为什么 .sort(() => Math.random() - 0.5) 是错的

JavaScript 的 sort() 不是为随机设计的：

1. 偏差 (Bias)：不同排列的概率不相等
2. 依赖排序实现：不同引擎的排序算法不同（V8 用 Timsort，Firefox 用归并排序），结果不可预测
3. 性能差：时间复杂度 O(n log n)，而 Fisher-Yates 是 O(n)

时间复杂度

• 时间：O(n)，只遍历一次
• 空间：O(1) 原地交换（如果不需要保留原数组）

应用场景

• 随机打乱数组（如洗牌、随机排序）
• 随机抽样（取前 k 个）
• 生成随机密码时打乱字符顺序

TypeScript 安全实现

function getSecureRandomInt(max: number): number {
  const array = new Uint32Array(1);
  crypto.getRandomValues(array);
  return array[0] % max;
}

function secureShuffle(array: string[]): string[] {
  const result = [...array];
  for (let i = result.length - 1; i > 0; i--) {
    const j = getSecureRandomInt(i + 1);
    [result[i], result[j]] = [result[j], result[i]];
  }
  return result;
}

Related notes

• 前端工程化MOC
• 前端基础MOC
• CSS MOC
• ECMAScript MOC