Fisher-Yates洗牌算法讲解(JS版本)

2024-08-24 23:04

本文主要是介绍Fisher-Yates洗牌算法讲解(JS版本),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

什么是洗牌算法?

洗牌算法是一种将一组数据(通常是数组)打乱顺序的算法,使得所有可能的排列组合都是等概率的。这个过程类似于我们在现实中洗扑克牌的过程:你希望打乱扑克牌,使其顺序完全随机。

Fisher-Yates 洗牌算法概述

Fisher-Yates 洗牌算法是最常用的洗牌算法之一,它能够在 O(n) 的时间内完成洗牌,并且确保每个可能的排列都具有相同的概率。该算法的基本思路是从数组的最后一个元素开始,依次将其与前面任意一个随机选中的元素交换位置。

Fisher-Yates 洗牌算法的步骤

  1. 从数组的最后一个元素开始

    • 选择一个范围从 0 到当前索引的随机索引 j
    • 将当前元素与索引 j 处的元素进行交换。
    • 将范围缩小,重复上述步骤,直到处理完所有元素。
  2. 核心思想

    • 每次从未洗牌的部分中随机选择一个元素进行交换,从而保证每个元素都有机会出现在数组的任意位置。

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);

代码解释:

  1. for (let i = array.length - 1; i > 0; i--):

    • 我们从数组的最后一个元素开始,依次向前遍历。
  2. const j = Math.floor(Math.random() * (i + 1));:

    • Math.random() 生成一个 0 到 1 之间的随机小数。
    • 乘以 i + 1 可以将这个随机数放大到 0i 之间,然后通过 Math.floor 取整,得到 0i 之间的随机整数 j
  3. 交换操作

    • array[i]array[j] 进行交换,确保 array[i] 被随机选中的元素替换。
  4. return array:

    • 返回已经打乱顺序的数组。

运行示例:

let arr = [1, 2, 3, 4, 5];
let shuffledArray = fisherYatesShuffle(arr);
console.log(shuffledArray); // 输出一个随机打乱的数组,例如 [3, 5, 1, 2, 4]

Fisher-Yates 洗牌算法的特点

  1. 效率: 该算法的时间复杂度为 O(n),因为它仅需要一次遍历数组,并且每次遍历中只进行常数时间的操作。

  2. 公平性: 每个元素被放置在任意位置的概率都是均等的,确保了所有可能的排列组合都具有相同的概率。

  3. 空间复杂度: 该算法在原数组上进行操作,因此它的空间复杂度是 O(1),即不需要额外的空间来存储中间结果。

Fisher-Yates 洗牌算法的应用

  1. 随机排序数据: 在需要随机排序的场合(如卡牌游戏、抽奖、测验题目等),Fisher-Yates 洗牌算法是非常理想的选择。

  2. 抽样: 在数据科学和统计分析中,Fisher-Yates 洗牌可以用于生成数据的随机样本。

  3. 随机选择: 需要从大量元素中随机选择一些元素时,也可以使用该算法。

  4. 蒙特卡罗模拟: 在随机模拟和蒙特卡罗方法中,Fisher-Yates 洗牌算法可以用于生成初始的随机排列。

这篇关于Fisher-Yates洗牌算法讲解(JS版本)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1103858

相关文章

IDEA如何切换数据库版本mysql5或mysql8

《IDEA如何切换数据库版本mysql5或mysql8》本文介绍了如何将IntelliJIDEA从MySQL5切换到MySQL8的详细步骤,包括下载MySQL8、安装、配置、停止旧服务、启动新服务以及... 目录问题描述解决方案第一步第二步第三步第四步第五步总结问题描述最近想开发一个新应用,想使用mysq

java脚本使用不同版本jdk的说明介绍

《java脚本使用不同版本jdk的说明介绍》本文介绍了在Java中执行JavaScript脚本的几种方式,包括使用ScriptEngine、Nashorn和GraalVM,ScriptEngine适用... 目录Java脚本使用不同版本jdk的说明1.使用ScriptEngine执行javascript2.

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

Debian如何查看系统版本? 7种轻松查看Debian版本信息的实用方法

《Debian如何查看系统版本?7种轻松查看Debian版本信息的实用方法》Debian是一个广泛使用的Linux发行版,用户有时需要查看其版本信息以进行系统管理、故障排除或兼容性检查,在Debia... 作为最受欢迎的 linux 发行版之一,Debian 的版本信息在日常使用和系统维护中起着至关重要的作

Node.js 中 http 模块的深度剖析与实战应用小结

《Node.js中http模块的深度剖析与实战应用小结》本文详细介绍了Node.js中的http模块,从创建HTTP服务器、处理请求与响应,到获取请求参数,每个环节都通过代码示例进行解析,旨在帮... 目录Node.js 中 http 模块的深度剖析与实战应用一、引言二、创建 HTTP 服务器:基石搭建(一

你的华为手机升级了吗? 鸿蒙NEXT多连推5.0.123版本变化颇多

《你的华为手机升级了吗?鸿蒙NEXT多连推5.0.123版本变化颇多》现在的手机系统更新可不仅仅是修修补补那么简单了,华为手机的鸿蒙系统最近可是动作频频,给用户们带来了不少惊喜... 为了让用户的使用体验变得很好,华为手机不仅发布了一系列给力的新机,还在操作系统方面进行了疯狂的发力。尤其是近期,不仅鸿蒙O

什么是 Ubuntu LTS?Ubuntu LTS和普通版本区别对比

《什么是UbuntuLTS?UbuntuLTS和普通版本区别对比》UbuntuLTS是Ubuntu操作系统的一个特殊版本,旨在提供更长时间的支持和稳定性,与常规的Ubuntu版本相比,LTS版... 如果你正打算安装 Ubuntu 系统,可能会被「LTS 版本」和「普通版本」给搞得一头雾水吧?尤其是对于刚入

windows端python版本管理工具pyenv-win安装使用

《windows端python版本管理工具pyenv-win安装使用》:本文主要介绍如何通过git方式下载和配置pyenv-win,包括下载、克隆仓库、配置环境变量等步骤,同时还详细介绍了如何使用... 目录pyenv-win 下载配置环境变量使用 pyenv-win 管理 python 版本一、安装 和

使用Vue.js报错:ReferenceError: “Vue is not defined“ 的原因与解决方案

《使用Vue.js报错:ReferenceError:“Vueisnotdefined“的原因与解决方案》在前端开发中,ReferenceError:Vueisnotdefined是一个常见... 目录一、错误描述二、错误成因分析三、解决方案1. 检查 vue.js 的引入方式2. 验证 npm 安装3.

JS常用组件收集

收集了一些平时遇到的前端比较优秀的组件,方便以后开发的时候查找!!! 函数工具: Lodash 页面固定: stickUp、jQuery.Pin 轮播: unslider、swiper 开关: switch 复选框: icheck 气泡: grumble 隐藏元素: Headroom