本文主要是介绍Fisher-Yates洗牌算法讲解(JS版本),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
什么是洗牌算法?
洗牌算法是一种将一组数据(通常是数组)打乱顺序的算法,使得所有可能的排列组合都是等概率的。这个过程类似于我们在现实中洗扑克牌的过程:你希望打乱扑克牌,使其顺序完全随机。
Fisher-Yates 洗牌算法概述
Fisher-Yates 洗牌算法是最常用的洗牌算法之一,它能够在 O(n) 的时间内完成洗牌,并且确保每个可能的排列都具有相同的概率。该算法的基本思路是从数组的最后一个元素开始,依次将其与前面任意一个随机选中的元素交换位置。
Fisher-Yates 洗牌算法的步骤
-
从数组的最后一个元素开始:
- 选择一个范围从 0 到当前索引的随机索引
j
。 - 将当前元素与索引
j
处的元素进行交换。 - 将范围缩小,重复上述步骤,直到处理完所有元素。
- 选择一个范围从 0 到当前索引的随机索引
-
核心思想:
- 每次从未洗牌的部分中随机选择一个元素进行交换,从而保证每个元素都有机会出现在数组的任意位置。
JavaScript 实现 Fisher-Yates 洗牌算法
以下是 Fisher-Yates 洗牌算法的 JavaScript 实现:
function fisherYatesShuffle(array) {// 从最后一个元素开始遍历数组for (let i = array.length - 1; i > 0; i--) {// 生成一个 0 到 i 之间的随机整数 jconst j = Math.floor(Math.random() * (i + 1));// 交换元素 array[i] 和 array[j][array[i], array[j]] = [array[j], array[i]];}return array; // 返回打乱后的数组
}// 示例使用
let arr = [1, 2, 3, 4, 5];
console.log("Original array:", arr);let shuffledArray = fisherYatesShuffle(arr);
console.log("Shuffled array:", shuffledArray);
代码解释:
-
for (let i = array.length - 1; i > 0; i--)
:- 我们从数组的最后一个元素开始,依次向前遍历。
-
const j = Math.floor(Math.random() * (i + 1));
:Math.random()
生成一个 0 到 1 之间的随机小数。- 乘以
i + 1
可以将这个随机数放大到0
到i
之间,然后通过Math.floor
取整,得到0
到i
之间的随机整数j
。
-
交换操作:
array[i]
和array[j]
进行交换,确保array[i]
被随机选中的元素替换。
-
return array
:- 返回已经打乱顺序的数组。
运行示例:
let arr = [1, 2, 3, 4, 5];
let shuffledArray = fisherYatesShuffle(arr);
console.log(shuffledArray); // 输出一个随机打乱的数组,例如 [3, 5, 1, 2, 4]
Fisher-Yates 洗牌算法的特点
-
效率: 该算法的时间复杂度为 O(n),因为它仅需要一次遍历数组,并且每次遍历中只进行常数时间的操作。
-
公平性: 每个元素被放置在任意位置的概率都是均等的,确保了所有可能的排列组合都具有相同的概率。
-
空间复杂度: 该算法在原数组上进行操作,因此它的空间复杂度是 O(1),即不需要额外的空间来存储中间结果。
Fisher-Yates 洗牌算法的应用
-
随机排序数据: 在需要随机排序的场合(如卡牌游戏、抽奖、测验题目等),Fisher-Yates 洗牌算法是非常理想的选择。
-
抽样: 在数据科学和统计分析中,Fisher-Yates 洗牌可以用于生成数据的随机样本。
-
随机选择: 需要从大量元素中随机选择一些元素时,也可以使用该算法。
-
蒙特卡罗模拟: 在随机模拟和蒙特卡罗方法中,Fisher-Yates 洗牌算法可以用于生成初始的随机排列。
这篇关于Fisher-Yates洗牌算法讲解(JS版本)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!