JS 洗牌算法

更新日期: 2019-07-29阅读: 2.6k标签: 算法

最近的一个塔罗牌项目中,有一个洗牌的需求,其实也就是随机打乱数组,遂网上搜了下,再此做个整理…

塔罗牌,举例来说,我们有一个如下图所示的数组,数组长度为 9,数组内元素的值顺次分别是 1~9:

1~9数组

从上面这个数组入手,我们要做的就是打乱数组内元素的顺序:


1~9数组打乱随机

代码实现

Array.prototype.shuffle = function () {
    let input = this;
    for (let i = input.length - 1; i >= 0; i--) {
        let randomIndex = Math.floor(Math.random() * (i + 1));
        let itemAtIndex = input[randomIndex];
        input[randomIndex] = input[i];
        input[i] = itemAtIndex;
    }
    return input;
}

在上面的代码中,我们创建了一个 shffle() 方法,该方法用于随机排列数组内的元素。

此外,我们将该方法挂载在了 Array 对象的原型下面,所以任何数组都可以直接调用该方法:

let tempArray = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
tempArray.shuffle();


工作原理

看完代码之后,让我们看看它对数组都做了写什么。首先,该方法选中数组的最后一个元素:


选择最后一个元素,接下来确定挑选随机元素的范围,从数组的第一个元素到上一步选中的元素都属于这一范围:

挑选随机元素范围

确定范围后,从中随机挑选一个数,这里假设随机选中的元素为 4:


随机挑选一个数

然后交换最后一个元素和随机选中的元素的值:


交换

上面的交换完成后,相当于我们完成了对数组最后一个元素的随机处理。接下来选中数组内倒数第二的元素:


处理倒数第二的元素

之所以从后往前处理,是因为这样便于确定随机选择的范围。这次我们假定随机到的元素为 2:


确定随机选择的范围

接着交换倒数第一个元素和 2 号元素的值,完成对倒数第二个元素随机排列的处理。然后是选中倒数第三个元素,重复之前的操作:


倒数第三个元素

剩下的就是一些重复性的工作,不多做介绍了。


分析代码

在上一节给各位用图例演示了洗牌流程,下面我们从代码本身看看洗牌流程。先从 shuffle 函数说起吧:

Array.prototype.shuffle = function () {
    let input = this;
    for (let i = input.length - 1; i >= 0; i--) {
        let randomIndex = Math.floor(Math.random() * (i + 1));
        let itemAtIndex = input[randomIndex];
        input[randomIndex] = input[i];
        input[i] = itemAtIndex;
    }
    return input;
}

shuffle 函数挂载在 Array 对象的原型之下,便于数组直接调用该函数。在 shuffle 函数内部,this 引用的就是调用该 shuffle 的数组:

var input = this;

在上面的代码中,我用一个新的变量引用 this,也就是调用 shuffle 函数的数组。 下一步,看一下 for 循环内都干了什么:

for (let i = input.length - 1; i >= 0; i--) {
    let randomIndex = Math.floor(Math.random() * (i + 1));
    let itemAtIndex = input[randomIndex];
    input[randomIndex] = input[i];
    input[i] = itemAtIndex;
}

该循环用于遍历所有数组内的所有元素,并进行随机交换。注意,遍历顺序是从后往前进行的,也就是说从input.length-1 位置的元素开始,知道遍历到数组中的第一个元素。遍历过程中的位置由变量 i 指定。

这里的变量 i 就是上面图例中被选中的元素


洗牌算法

接下来,使用了两行代码在指定范围内挑选一个随机元素:

let randomIndex = Math.floor(Math.random() * (i + 1));
let itemAtIndex = input[randomIndex];

变量 randomIndex 存储了一个随机数,该随机数可以用作数组的索引,进而提取一个随机元素。注意,该随机数的最大值并不是数组的长度,而是变量 i 的值。

确定了随机元素的索引之后,用新的变量保存该元素的值,然后交换选中元素和随机元素的值:

//使用新的变量保存了随机元素的值
let itemAtIndex = input[randomIndex];
//将选中元素 input[i] 的值赋给随机元素 input[randomIndex]
input[randomIndex] = input[i];
//随机元素的值 itemAtIndex 赋给选中元素 input[i]
input[i] = itemAtIndex;

本质上是一个互换两个元素的值的过程,并不难理解。至此,循环内的逻辑就介绍完了,剩下的都是重复操作。


随机性测试


上图是使用 Highcharts 制作的随机性测试图表,以可视化的方式校验本文中洗牌算法的随机性。每次刷新页面都会重新计算和生成该图表。

生成上图的数据是这样计算而来的:首先创建一个数组(上图使用的数组为 [0, 1, 2 … 18, 19, 20]),然后使用本文中的洗牌算法重新排序,排序完成后记录每一个元素的值……以此步骤执行 100000 次,最后对同一索引位置上的数值进行求和。如此执行 10000 次之后,索引之间的总值应该相差不大。

由计算可得:


原文 https://mp.weixin.qq.com/s/MNcHVl7WlP0gSpZYeiBJqg

链接: https://www.fly63.com/article/detial/5005

js洗牌算法:javascript数组随机打乱顺序的实现方法

有一个数组,我们需要通过js对数组的元素进行随机排序,然后输出,这其实就是洗牌算法,首页需要从元素中随机取一个和第一元进行交换,然后依次类推,直到最后一个元素。

程序员必须知道的10大基础实用算法及其讲解

程序员必须知道的10大算法:快速排序算法、堆排序算法、归并排序、二分查找算法、BFPRT(线性查找算法)、DFS(深度优先搜索)、BFS(广度优先搜索)、Dijkstra算法、动态规划算法、朴素贝叶斯分类算法

js从数组取出 连续的 数字_实现一维数组中连续数字分成几个连续的数字数组

使用原生js将一维数组中,包含连续的数字分成一个二维数组,这篇文章分2种情况介绍如何实现?1、过滤单个数字;2、包含单个数字。

原生Js获取数组中最长的连续数字序列的方法

给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。

Tracking.js_ js人脸识别前端代码/算法框架

racking.js 是一个独立的JavaScript库,实现多人同时检测人脸并将区域限定范围内的人脸标识出来,并保存为图片格式,跟踪的数据既可以是颜色,也可以是人,也就是说我们可以通过检测到某特定颜色,或者检测一个人体/脸的出现与移动,来触发JavaScript 事件。

JS常见算法题目

JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题

RSA算法详解

这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述,RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。

PageRank算法的定义与来源、以及PageRank算法原理

PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。

js算法_js判断一个字符串是否是回文字符串

什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a

js之反转整数算法

将一个整数中的数字进行颠倒,当颠倒后的整数溢出时,返回 0 ;当尾数为0时候需要进行舍去。解法:转字符串 再转数组进行操作,看到有人用四则运算+遍历反转整数。

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!