Js数组随机排序的实现_洗牌算法

更新日期: 2021-10-13阅读: 1.3k标签: 数组

JavaScript中提供了sort()和reverse()方法对数组项重新排序。但很多时候这两个方法无法满足我们实际业务的需求,比如说扑克牌游戏中的随机洗牌,例如:

我有一个这样的数组,我怎样才能随机化/洗牌呢?

var arr = [2, 11, 37, 42];


 Fisher-Yates(又名 Knuth)洗牌

function shuffle(array) {
let currentIndex = array.length, randomIndex;
while (currentIndex != 0) {
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex--;
[array[currentIndex], array[randomIndex]] = [
array[randomIndex], array[currentIndex]];
}
return array;
}

var arr = [2, 11, 37, 42];
shuffle(arr);
console.log(arr);


 Fisher-Yates优化版本

这是Durstenfeld shuffle的 JavaScript 实现,这是 Fisher-Yates 的优化版本:

/* Randomize array in-place using Durstenfeld shuffle algorithm */
function shuffleArray(array) {
    for (var i = array.length - 1; i > 0; i--) {
        var j = Math.floor(Math.random() * (i + 1));
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

它为每个原始数组元素选择一个随机元素,并将其从下一次抽奖中排除,就像从一副纸牌中随机选择一样。

这种巧妙的排除将选取的元素与当前元素交换,然后从余数中选取下一个随机元素,向后循环以获得最佳效率,确保随机选取得到简化(它始终可以从 0 开始),从而跳过最后一个元素。

算法运行时是O(n). 请注意,shuffle 是就地完成的,因此如果您不想修改原始数组,请先使用.slice(0).

ES6 / ECMAScript 2015

新的 ES6 允许我们一次分配两个变量。这在我们想要交换两个变量的值时特别方便,因为我们可以在一行代码中完成。这是使用此功能的相同功能的较短形式。

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


使用 map 和 sort 

let unshuffled = ['hello', 'a', 't', 'q', 1, 2, 3, {cats: true}]

let shuffled = unshuffled
  .map((value) => ({ value, sort: Math.random() }))
  .sort((a, b) => a.sort - b.sort)
  .map(({ value }) => value)
  1. 我们将数组中的每个元素放在一个对象中,并赋予它一个随机排序键
  2. 我们使用随机键排序
  3. 我们取消映射以获取原始对象

您可以对多态数组进行 shuffle,并且排序与 Math.random 一样随机,这对于大多数用途来说已经足够了。

由于元素根据每次迭代都不会重新生成的一致键进行排序,并且每次比较都从相同的分布中提取,因此 Math.random 分布中的任何非随机性都被抵消了。

速度

时间复杂度为 O(N log N),与快速排序相同。空间复杂度为 O(N)。这不如 Fischer Yates shuffle 有效,但在我看来,代码明显更短且功能更强大。如果你有一个大数组,你当然应该使用 Fischer Yates。如果你有一个包含几百个项目的小数组,你可以这样做。


其他解决方案

其他解决方案只是为了好玩。

ES6 纯递归

    const getShuffledArr = arr => {
        if (arr.length === 1) {return arr};
        const rand = Math.floor(Math.random() * arr.length);
        return [arr[rand], ...getShuffledArr(arr.filter((_, i) => i != rand))];
    };

ES6 Pure 使用 array.map

    function getShuffledArr (arr){
        return [...arr].map( (_, i, arrCopy) => {
            var rand = i + ( Math.floor( Math.random() * (arrCopy.length - i) ) );
            [arrCopy[rand], arrCopy[i]] = [arrCopy[i], arrCopy[rand]]
            return arrCopy[i]
        })
    }

ES6 Pure 使用 array.reduce

    function getShuffledArr (arr){
        return arr.reduce( 
            (newArr, _, i) => {
                var rand = i + ( Math.floor( Math.random() * (newArr.length - i) ) );
                [newArr[rand], newArr[i]] = [newArr[i], newArr[rand]]
                return newArr
            }, [...arr]
        )
    }

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

探索JavaScript数组奥秘

avaScript数组同后端语言一样,具有它自己的数据结构,归根结底,这种数据结构,本质就是一种集合。在后端语言中(如java,.net等),数组是这样定义的:数组是用来存储相同数据类型的集合

js使用数组+循环+条件实现数字转换为汉字的简单方法。

单个数字转汉字的解决方法:利用数组存储0-9的汉字、 ary.length和str.length不用多说,这是指ary数组和str字符串的长度。这里我们需要注意的是str.charAt(j)和ary[i],分别指在str这个字符串中索引为j的元素,在ary中索引为i的元素。

[译]async-await 数组循环的几个坑

在 Javascript 循环中使用 async/ await 循环遍历数组似乎很简单,但是在将两者结合使用时需要注意一些非直观的行为。让我们看看三个不同的例子,看看你应该注意什么,以及哪个循环最适合特定用例。

数组、字符串去重

今天说的数组和字符串去重呢,主要用到es6新的数据结构 Set,它类似于数组,但是成员的值都是唯一的,没有重复的值,所以活用Set来进行数组和字符串的去重。

JavaScript 数组方法

数组方法:1、Array.join([param]) 方法:将数组中所有的元素都转换为字符串并连接起来,通过字符 param 连接,默认使用逗号,返回最后生成的字符串2、Array.reverse() 方法:将数组中的元素颠倒顺序(在原数组中重新排列它们),返回逆序数组

如何删除JavaScript 数组中的虚值

falsy(虚值)是在 Boolean 上下文中已认定可转换为‘假‘的值.JavaScript 在需要用到布尔类型值的上下文中使用强制类型转换(Type Conversion )将值转换为布尔值,比如:在条件语句或者循环语句中。

JavaScript中十种一步拷贝数组的方法

JavaScript中我们经常会遇到拷贝数组的场景,但是都有哪些方式能够来实现呢,我们不妨来梳理一下。扩展运算符(浅拷贝)自从ES6出现以来,这已经成为最流行的方法。

JS数组的几个经典api

本文主要来讲数组api的一些操作,如简单实现扁平化n维数组、数组去重、求数组最大值、数组求和、排序、对象和数组的转化等。扁平化嵌套数组/展平和阵列孔——flat()

关于Vue不能监听(watch)数组变化

vue无法监听数组变化的情况,但是数组在下面两种情况下无法监听:利用索引直接设置数组项时,例如arr[indexofitem]=newValue;修改数组的长度时,例如arr.length=newLength

JS计算两个数组的交集、差集、并集、补集(多种实现方式)

使用 ES5 语法来实现虽然会麻烦些,但兼容性最好,不用考虑浏览器 JavaScript 版本,使用 ES5 语法来实现虽然会麻烦些,但兼容性最好,不用考虑浏览器 JavaScript 版本。也不用引入其他第三方库。

点击更多...

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