手写数组洗牌算法

技术文档

手写数组洗牌算法

问题描述

实现一个数组洗牌函数，使用Fisher-Yates（费雪-耶茨）洗牌算法，确保数组元素随机排列，每个元素在每个位置上的概率相等。

输入：一个数组
输出：洗牌后的数组（原地洗牌）

问题分析

Fisher-Yates洗牌算法的核心思想是：

从数组的末尾开始向前遍历
对于每个元素，随机选择一个在它之前（包括它自己）的元素
交换这两个元素
继续遍历，直到处理完所有元素

这种方法可以确保每个元素都有均等的机会被放置在任何位置，并且时间复杂度为O(n)，空间复杂度为O(1)。

代码实现

/** * 手写数组洗牌算法（Fisher-Yates算法） * @param {Array} array - 需要洗牌的数组 * @returns {Array} 洗牌后的数组（原地修改） */function shuffleArray(array) { // 从数组末尾开始遍历 for (let i = array.length - 1; i > 0; i--) { // 随机生成一个[0, i]之间的整数 const j = Math.floor(Math.random() * (i + 1)); // 交换元素 [array[i], array[j]] = [array[j], array[i]]; } return array;}

调用示例

// 示例1：基本使用const arr1 = [1, 2, 3, 4, 5];shuffleArray(arr1);console.log(arr1); // 输出可能为：[3, 1, 5, 2, 4]// 示例2：包含不同类型元素const arr2 = [\'a\', \'b\', \'c\', 1, 2, 3];shuffleArray(arr2);console.log(arr2); // 输出可能为：[2, \'a\', 3, \'c\', 1, \'b\']// 示例3：空数组或单元素数组const arr3 = [];console.log(shuffleArray(arr3)); // 输出：[]const arr4 = [42];console.log(shuffleArray(arr4)); // 输出：[42]

执行过程解析

以数组[1, 2, 3, 4]为例，执行过程如下：

初始数组：[1, 2, 3, 4]
i = 3（最后一个元素）：
- 生成j = Math.floor(Math.random() * 4)，假设j = 1
- 交换array[3]和array[1]：[1, 4, 3, 2]
i = 2：
- 生成j = Math.floor(Math.random() * 3)，假设j = 0
- 交换array[2]和array[0]：[3, 4, 1, 2]
i = 1：
- 生成j = Math.floor(Math.random() * 2)，假设j = 1
- 交换array[1]和array[1]（不改变）：[3, 4, 1, 2]
最终结果：[3, 4, 1, 2]

复杂度分析

时间复杂度：O(n)，其中n是数组的长度。只需遍历一次数组。
空间复杂度：O(1)，只使用了常数级别的额外空间，实现了原地洗牌。

常见错误与注意事项

错误的循环条件：

// 错误示例：循环条件错误function wrongShuffle(array) { for (let i = 0; i < array.length; i++) { const j = Math.floor(Math.random() * array.length); [array[i], array[j]] = [array[j], array[i]]; } return array;}

这种实现会导致元素概率不均等，某些元素更可能停留在原位置。

随机索引范围错误：
- 错误写法：Math.random() * i（缺少+1）
- 正确写法：Math.random() * (i + 1)（包含+1）
- 错误原因：
  - Math.random() 返回 [0, 1) 区间的浮点数（包含0但不包含1）
  - 当乘以 i 时，结果范围是 [0, i)（包含0但不包含i）
  - 使用 Math.floor() 后，得到的整数范围是 [0, i-1]，永远无法取到i
- 数学证明：
  - 假设当前索引 i = 3（数组第4个元素）
  - 错误写法：Math.random() * 3 → 结果范围 [0, 3) → 取整后可能值：0, 1, 2（共3种可能）
  - 正确写法：Math.random() * 4 → 结果范围 [0, 4) → 取整后可能值：0, 1, 2, 3（共4种可能）
- 导致后果：
  - 最后一个元素（索引i）永远不会被选中交换
  - 数组末尾元素的位置固定，无法被随机化
  - 整体洗牌结果非均匀分布，出现系统性偏差
- 可视化示例（i=3时）：
```
错误写法范围：[0,3) → 可能索引：0,1,2（缺少3）正确写法范围：[0,4) → 可能索引：0,1,2,3（完整覆盖）
```
数组越界：确保随机数生成在有效范围内

面试常见问题

问题1：为什么Fisher-Yates算法比简单交换更公平？

答：简单交换（如随机交换任意两个元素）会导致概率不均等，某些排列出现的概率更高。Fisher-Yates算法通过从后向前遍历并限制随机选择范围，确保每个元素有相等的概率被放置在任何位置。数学上可以证明，该算法能产生均匀分布的随机排列。

问题2：如何实现不修改原数组的洗牌算法？

答：可以先创建数组的副本，然后对副本执行洗牌操作：

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

问题3：Math.random()有什么潜在问题？如何改进？

答：Math.random()生成的是伪随机数，在加密场景下不够安全。可以使用crypto API提供的更安全的随机数生成器：

function secureShuffle(array) { const newArray = [...array]; for (let i = newArray.length - 1; i > 0; i--) { const j = Math.floor(crypto.getRandomValues(new Uint32Array(1))[0] / (0xFFFFFFFF + 1) * (i + 1)); [newArray[i], newArray[j]] = [newArray[j], newArray[i]]; } return newArray;}

问题4：如何测试洗牌算法的随机性？

答：可以通过大量重复试验，统计每个元素出现在每个位置的频率，看是否接近均匀分布：

function testShuffleAlgorithm(shuffleFunc, arrayLength = 4, trials = 100000) { const counts = Array.from({ length: arrayLength }, () => Array(arrayLength).fill(0)); for (let i = 0; i < trials; i++) { const testArray = Array.from({ length: arrayLength }, (_, idx) => idx); const shuffled = shuffleFunc(testArray); shuffled.forEach((val, pos) => counts[val][pos]++); } // 计算每个位置的频率 const frequencies = counts.map(row => row.map(count => count / trials)); return frequencies;}

理想情况下，每个频率应接近1/arrayLength。

手写数组洗牌算法