JS实现数组随机排序的三种方法详解

目录
  • 1.利用数组方法sort实现随机排序
  • 2.洗牌算法实现随机排序
  • 3.洗牌算法深入分析
  • 全部代码

1.利用数组方法sort实现随机排序

实现随机排序方法还是很多的，用for循环是可以写的，用Lodash等三方js方法库也行。但个人以为使用sort比较方便，但是他又缺点，缺点就是不够那么的随机，我看过sort运行机制后，发现他竟然是利用一个比较器两两比较出来的。

var arr = [1, 2, 3, 4, 5]

arr.sort(function () {
  return Math.random() - 0.5
})
console.log(arr);

2.洗牌算法实现随机排序

从原始数组中每次随机选中一个元素，然后放入新数组中，每取出一个元素后，将将它从原数组中取出（使用splice方法），原数组长度减一。

举例：

现在我有红桃K、黑桃A、小王三张牌，要求打乱顺序，你可以从三张牌抽出任意一张，假设你抽到的是小王，那么我手里三张牌变成两张牌，你手里变成1张牌，以此类推，实现随机排序。

代码实现：

function shuffle(array){
    let res = [], random;
    while(array.length>0){
        random = Math.floor(Math.random()*array.length);
        res.push(array[random]);
        array.splice(random, 1);
    }
    return res;
}

console.log(shuffle([1,2,3,4,5]));

3.洗牌算法深入分析

思路：我有一副牌，随机抽取牌，旧的牌数量相应减少!

function shuffle(m) //洗牌 //抽牌法
{
//生成m张牌
var arr = new Array(m);
for (var i=0; i<m; i++) {
arr[i] = i;
}
//每次抽出一张牌，需要遍历整个数组，所以很耗时。
var arr2 = new Array();
for (var i=m; i>0; i–) {
var rnd = Math.floor(Math.random()*i);
arr2.push(arr[rnd]);
arr.splice(rnd,1);
}
return arr2;
}

但是这样的话，因为数组如果很大的话，删除中间的某个元素，会导致后面的数据被执行，会对性能影响很大。

我们删除那个元素的目的就是为了不产生空牌。

除了删除那个元素之外，我们是不是还有其它方式来去除空牌？

只需把最后一张未抽的牌放在那个抽走的位置上就可以了。

顺着这个思路我们可以优化成这样：

代码如下:

function shuffle_pick(m) //洗牌 //抽牌法优化牌
{
//生成m张牌
var arr = new Array(m);
for (var i=0; i<m; i++) {
arr[i] = i;
}
//每次抽出一张牌，放在另一堆。把最后一张未抽的牌放在空位子上。
var arr2 = new Array();
for (var i=m; i>0;) {
var rnd = Math.floor(Math.random()*i);
arr2.push(arr[rnd]);
arr[rnd] = arr[–i];
}
return arr2;
}

除了抽牌思路，我们还可以用换牌思路：

“随机交换两个位置，共交换n次，n越大，越接近随机”。

顺着这个思路，做一点小调整就可以了：第i张与任意一张牌换位子，换完一轮即可。

代码如下:

function shuffle_swap(m) //洗牌 //换牌法
{
//生成m张牌
var arr = new Array(m);
for (var i=0; i<m; i++) {
arr[i] = i;
}
//第i张与任意一张牌换位子，换完一轮即可
for (var i=0; i<m; i++) {
var rnd = Math.floor(Math.random()*(i+1)),
temp = arr[rnd];
arr[rnd] = arr[i];
arr[i]=temp;
}
return arr;
}

除了抽牌与换牌的思路，我们还可以用插牌的思路：先有一张牌，第二张牌有两个位置可随机插入（第一张牌前，或后），第三张牌有三个位置可随机插入（放在后面，或插在第一位，或插在第二位），依此类推

代码如下:

function shuffle_insert_1(m) //洗牌 //插牌法
{
//每次生成一张最大的牌，插在随机的某张牌前。因为要在数组里插入元素，把后面的所有元素向后挤一位，所以很耗时。
var arr = [0];
for (var i=1; i<m; i++) {
arr.splice(Math.floor(Math.random()*(i+1)),0,i);
}
return arr;
}

以上的代码也会有一些问题：就是随着牌数的增多，插牌变得越来越困难，因为插牌会导致后面的很多牌都往后推一步。

当然，我们也可以适当的优化一下：先有n-1张牌，第n张牌放在最后，然后与任意一张牌互换位置。

代码如下：

function shuffle_insert(m) //洗牌 //插牌法优化版，可以用数学归纳法证明，这种洗牌是均匀的。
{
//每次生成一张最大的牌，与随机的某张牌换位子
var arr = new Array(m);
arr[0] = 0;
for (var i=1; i<m; i++) {
var rnd = Math.floor(Math.random()*(i+1));
arr[i] = arr[rnd];
arr[rnd] = i;
}
return arr;
}

全部代码

代码如下:

<html>
<head>
<meta http-equiv=”Content-Type” content=”text/html; charset=gb2312″>
<title>JK：javascript 洗牌算法 </title>
</head>
<body>
<script type=”text/javascript”>
function shuffle_pick_1(m) //洗牌 //抽牌法
{
//生成m张牌
var arr = new Array(m);
for (var i=0; i<m; i++) {
arr[i] = i;
}
//每次抽出一张牌，放在另一堆。因为要在数组里抽出元素，把后面的所有元素向前拉一位，所以很耗时。
var arr2 = new Array();
for (var i=m; i>0; i–) {
var rnd = Math.floor(Math.random()*i);
arr2.push(arr[rnd]);
arr.splice(rnd,1);
}
return arr2;
}
function shuffle_pick(m) //洗牌 //抽牌法优化牌
{
//生成m张牌
var arr = new Array(m);
for (var i=0; i<m; i++) {
arr[i] = i;
}
//每次抽出一张牌，放在另一堆。把最后一张未抽的牌放在空位子上。
var arr2 = new Array();
for (var i=m; i>0;) {
var rnd = Math.floor(Math.random()*i);
arr2.push(arr[rnd]);
arr[rnd] = arr[–i];
}
return arr2;
}
function shuffle_swap(m) //洗牌 //换牌法
{
//生成m张牌
var arr = new Array(m);
for (var i=0; i<m; i++) {
arr[i] = i;
}
//第i张与任意一张牌换位子，换完一轮即可
for (var i=0; i<m; i++) {
var rnd = Math.floor(Math.random()*(i+1)),
temp = arr[rnd];
arr[rnd] = arr[i];
arr[i]=temp;
}
return arr;
}
function shuffle_insert_1(m) //洗牌 //插牌法
{
//每次生成一张最大的牌，插在随机的某张牌前。因为要在数组里插入元素，把后面的所有元素向后挤一位，所以很耗时。
var arr = [0];
for (var i=1; i<m; i++) {
arr.splice(Math.floor(Math.random()*(i+1)),0,i);
}
return arr;
}
function shuffle_insert(m) //洗牌 //插牌法优化版，可以用数学归纳法证明，这种洗牌是均匀的。
{
//每次生成一张最大的牌，与随机的某张牌换位子
var arr = new Array(m);
arr[0] = 0;
for (var i=1; i<m; i++) {
var rnd = Math.floor(Math.random()*(i+1));
arr[i] = arr[rnd];
arr[rnd] = i;
}
return arr;
}
//alert(shuffle_pick(10))
var funcs = [shuffle_pick_1, shuffle_pick, shuffle_swap, shuffle_insert_1, shuffle_insert],
funcNames = [“抽牌”, “抽牌优化”, “换牌”, “插牌”, “插牌优化”]
m = 10000,
times=[];
for(var i = 0; i < funcs.length; i++){
var d0= new Date();
funcs[i](m);
funcNames[i] = (new Date() – d0) + ‘\t' + funcNames[i];
}
alert(funcNames.join(‘\n'));
</script>
</body>
</html>

到此这篇关于JS实现数组随机排序的方法详解的文章就介绍到这了,更多相关JS数组随机排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • JavaScript实现数组随机排序的方法

    本文实例讲述了JavaScript实现数组随机排序的方法.分享给大家供大家参考.具体实现方法如下: function Shuffle(o) { for(var j, x, i = o.length; i; j = parseInt(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x); return o; }; 使用方法: var testArray = [1,2,3,4,5]; Shuffle(testArray); // jQuery

  • javascript数组随机排序实例分析

    本文实例讲述了javascript数组随机排序实现方法.分享给大家供大家参考.具体如下: 我们就测试0-9的随机排序,先生成数据 var arr=[9,3,1,2,5,8,4,7,6,0]; arr.sort(); document.write("正常排序后的数组元素:"+arr.join(",")+"<BR />"); 正常排序后的数组元素:0,1,2,3,4,5,6,7,8,9 定义一个随机函数,随机返回正数或者负数,sort函数

  • JS随机洗牌算法之数组随机排序

    JS随机洗牌算法之数组随机排序

    推荐阅读:JavaScript学习笔记之数组的增.删.改.查 JavaScript学习笔记之数组求和方法 JavaScript学习笔记之数组随机排序 洗牌算法是一个比较形象的术语,本质上让一个数组内的元素随机排列.举例来说,我们有一个如下图所示的数组,数组长度为 9,数组内元素的值顺次分别是 1~9: 从上面这个数组入手,我们要做的就是打乱数组内元素的顺序: 代码实现 维基百科上的 Fisher–Yates shuffle 词条对洗牌算法做了详细介绍,下面演示的算法也是基于其中的理论编写的: A

  • JS随机排序数组实现方法分析

    本文实例讲述了JS随机排序数组.分享给大家供大家参考,具体如下: 做随机显示推荐广告的时候,需要随机排序数据数组,就动手写了一个,如下: function randomOrder (targetArr) { var originalArr = targetArr; var newArr = []; var arrLength = targetArr.length; var j = -1; var tmpObj = {}; for(var i = 0;i < arrLength;i++){ whi

  • JavaScript学习笔记之数组随机排序

    JavaScript学习笔记之数组随机排序

    推荐阅读:JavaScript学习笔记之数组求和方法 JavaScript学习笔记之数组的增.删.改.查 JavaScript中提供了sort()和reverse()方法对数组项重新排序.但很多时候这两个方法无法满足我们实际业务的需求,比如说扑克牌游戏中的随机洗牌. 在这篇文章一起来学习如何完成上面这个示例的效果,以及一些有关于数组随机排序的相关知识. 在网上查了一下有关于数组随机排序的相关资料,都看到了Math.random()的身影.打开浏览器控制器,输入: Math.random() 从图

  • JS实现数组随机排序的三种方法详解

    JS实现数组随机排序的三种方法详解

    目录 1.利用数组方法sort实现随机排序 2.洗牌算法实现随机排序 3.洗牌算法深入分析 全部代码 1.利用数组方法sort实现随机排序 实现随机排序方法还是很多的,用for循环是可以写的,用Lodash等三方js方法库也行.但个人以为使用sort比较方便,但是他又缺点,缺点就是不够那么的随机,我看过sort运行机制后,发现他竟然是利用一个比较器两两比较出来的. var arr = [1, 2, 3, 4, 5] arr.sort(function () { return Math.rando

  • JavaScript中数组去重常用的五种方法详解

    目录 1.对象属性(indexof) 2.new Set(数组) 3.new Map() 4.filter() + indexof 5.reduce() + includes 补充 原数组 const arr = [1, 1, '1', 17, true, true, false, false, 'true', 'a', {}, {}]; 1.对象属性(indexof) 利用对象属性key排除重复项 遍历数组,每次判断新数组中是否存在该属性,不存在就存储在新数组中 并把数组元素作为key,最后返

  • Python实现解析参数的三种方法详解

    Python实现解析参数的三种方法详解

    目录 先决条件 使用 argparse 使用 JSON 文件 使用 YAML 文件 最后的想法 今天我们分享的主要目的就是通过在 Python 中使用命令行和配置文件来提高代码的效率 Let's go! 我们以机器学习当中的调参过程来进行实践,有三种方式可供选择.第一个选项是使用 argparse,它是一个流行的 Python 模块,专门用于命令行解析:另一种方法是读取 JSON 文件,我们可以在其中放置所有超参数:第三种也是鲜为人知的方法是使用 YAML 文件!好奇吗,让我们开始吧! 先决条件

  • python解析命令行参数的三种方法详解

    python解析命令行参数的三种方法详解

    这篇文章主要介绍了python解析命令行参数的三种方法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 python解析命令行参数主要有三种方法:sys.argv.argparse解析.getopt解析 方法一:sys.argv -- 命令行执行:python test_命令行传参.py 1,2,3 1000 # test_命令行传参.py import sys def para_input(): print(len(sys.argv)) #

  • SpringMVC统一异常处理三种方法详解

    这篇文章主要介绍了SpringMVC-统一异常处理三种方法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 在 Spring MVC 应用的开发中,不管是对底层数据库操作,还是业务层或控制层操作,都会不可避免地遇到各种可预知的.不可预知的异常需要处理. 如果每个过程都单独处理异常,那么系统的代码耦合度高,工作量大且不好统一,以后维护的工作量也很大. 如果能将所有类型的异常处理从各层中解耦出来,这样既保证了相关处理过程的功能单一,又实现了异常信

  • Mybatis 逆向工程的三种方法详解

    Mybatis 逆向工程的三种方法详解

    Mybatis 逆向工程   逆向工程通常包括由数据库的表生成 Java 代码 和 通过 Java 代码生成数据库表.而Mybatis 逆向工程是指由数据库表生成 Java 代码.   Mybaits 需要程序员自己编写 SQL 语句,但是 Mybatis 官方提供逆向工程可以针对单表自动生成 Mybaits 执行所需要的代码,包括 POJO.Mapper.java.Mapper.xml -. 一.通过 Eclipse 插件完成 Mybatis 逆向工程 1. 在线安装 Eclipse 插件  

  • Android开发之保存图片到相册的三种方法详解

    目录 方法一 方法二 方法三 有三种方法如下:三个方法都需要动态申请读写权限否则保存图片到相册也会失败 方法一 /** * 保存bitmap到本地 * * @param bitmap Bitmap */ public static void saveBitmap(Bitmap bitmap, String path) { String savePath; File filePic; if (Environment.getExternalStorageState().equals(Environm

  • Python中提取人脸特征的三种方法详解

    目录 1.直接使用dlib 2.使用深度学习方法查找人脸,dlib提取特征 3.使用insightface提取人脸特征 安装InsightFace 提取特征 1.直接使用dlib 安装dlib方法: Win10安装dlib GPU过程详解 思路: 1.使用dlib.get_frontal_face_detector()方法检测人脸的位置. 2.使用 dlib.shape_predictor()方法得到人脸的关键点. 3.使用dlib.face_recognition_model_v1()方法提取

  • Java比较两个对象大小的三种方法详解

    Java比较两个对象大小的三种方法详解

    目录 一. 为什么需要比较对象 二. 元素的比较 1. 基本类型的比较 2. 引用类型的比较 三. 对象比较的方法 1. equals方法比较 2. 基于Comparable接口的比较 3. 基于Comparator接口的比较 4. 三种比较方式对比 一. 为什么需要比较对象 上一节介绍了优先级队列,在优先级队列中插入的元素必须能比较大小,如果不能比较大小,如插入两个学生类型的元素,会报ClassCastException异常 示例: class Student{ String name; in

  • C语言实现短字符串压缩的三种方法详解

    C语言实现短字符串压缩的三种方法详解

    目录 前言 一.通用算法的短字符压缩 二.短字符串压缩 (1)Smaz (2)Shoco (3)Unisox2 三.总结 前言 上一篇探索了LZ4的压缩和解压性能,以及对LZ4和ZSTD的压缩.解压性能进行了横向对比.文末的最后也给了一个彩蛋:任意长度的字符串都可以被ZSTD.LZ4之类的压缩算压缩得很好吗? 本篇我们就来一探究竟. 一.通用算法的短字符压缩 开门见山,我们使用一段比较短的文本:Narrator: It is raining today. So, Peppa and George

随机推荐