Fisher-Yates 洗牌算法
Fisher-Yates (Knuth) 洗牌算法，保证等概率打乱数组的唯一正确方法。
#type / concept
#status / evergreen
#resource / algorithm
#resource / javascript
#tech / dev / frontend
#algo / sort
[!info] related notes
- 所属 MOC: 算法面试题型 MOC
- 并列概念: quicksort, randomized-select
- 易混淆:
.sort(() => Math.random() - 0.5)是错误的洗牌方式- 安全场景: crypto.getRandomValues
Fisher-Yates 洗牌算法
一句话定义
Fisher-Yates 洗牌算法通过从后往前遍历，每次在 [0, i] 范围内随机选一个位置交换，保证每个元素落在每个位置的概率严格相等。
核心机制
- 从数组最后一个元素开始，向前遍历
- 对于位置
i，在[0, i]范围内随机选一个索引j - 交换
arr[i]和arr[j] - 重复直到遍历完所有元素
最小例子
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() 不是为随机设计的：
- 偏差 (Bias)：不同排列的概率不相等
- 依赖排序实现：不同引擎的排序算法不同（V8 用 Timsort，Firefox 用归并排序），结果不可预测
- 性能差：时间复杂度
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;
}