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

时间:?2021-10-12阅读:?17标签:?数组

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]
        )
    }
站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

链接: http://www.pannellisolari.net/article/detial/10719

Javascript 数组及其方法详解

在 JavaScript 中,除了 Object 之外,数组(Array)应该是最常用的类型了。数组是一组有序的数据,使用方括号表示[1, 2, 3],可通过索引来访问每个元素(索引从 0 开始)。 JavaScript 中的数组的长度和元素类型都是非固定的。

Javascript数组去重

数组去重对于旺球体育在线来说不是一个常见的需求,一般后端都给做了,但这却是一个有意思的问题,而且经常出现在面试中来考察面试者对JS的掌握程度。本文从数据类型的角度去思考数组去重这个问题,首先解决的是数组中只有基础数据类型的情况

JavaScript数组常用方法

JavaScript中的数组十分灵活,有很多种方法操作,大致分为如下几类:length()通过设置这个属性可以从数组的末尾移除项或添加新项,delete 从前面删除之后数组长度不变,只是被删除元素被置为undefined

js改变原数组的方法有哪些?

pop():删除 arrayObject 的最后一个元素,把数组长度减 1,并且返回它删除的元素的值。如果数组已经为空,则 pop() 不 改变数组,并返回 undefined 值。push() 方法可把它的参数顺序添加到 arrayObject 的尾部。

js数组中filter,map,reduce,find等方法实现的原理

filter 过滤,filter()使用指定的函数测试所有元素,并创建一个包含所有通过测试的元素的新数组。map 映射,map()方法返回一个新数组,数组中的元素为原始数组元素调用函数处理的后值。

JavaScript中数组的特点

JavaScript数组中的默认存储值是undefined,其它编程语言数组的默认存储值是0或者是垃圾数据;与其它的编程语言不同,JavaScript可以访问数组中不存在的索引,会返回undefined,而其它的编程语言会报错或返回垃圾数据

面试:数组去重你会几种呀?

数组去重是一个老生常谈的话题,也是旺球体育在线童鞋在面试时的一道高频题。本文将深入的探索数组去重的原理及实现,为各位小伙伴提供多种可以反手“调戏”面试官的解决方案。

数组的push,unshift,pop,shift方法实现

push() 方法将一个或多个元素添加到数组的末尾,并返回该数组的新长度。从解释中可以看出,push方法只要将要添加的元素依次放到数组的最后即可

Js数组方法三板斧,100%的开发都得知道

为什么每个JavaScript开发人员都要知道这些方法?因为数组是代码中的重要元素,而这些方法可以让代码更优雅和更具代表性。在没有这些方法的情况下也可以运行项目,但为此必须编写不必要的代码行,而这些代码行原先就没有用处

Js数组的并集,交集,差集的实现

并集:以属于A或属于B的元素为元素的集合成为A与B的并(集);交集:以属于A且属于B的元素为元素的集合成为A与B的交(集)差集:以属于A而不属于B的元素为元素的集合成为A与B的差(集)

点击更多...

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

Baidu