数组随机排序：洗牌算法(Fisher–Yates shuffle)

张金宝发布于2019-08-20 15:27 / 619人阅读

摘要：代码实现代码一测试用例输出其中，代码二测试用例输出其中，参考资料洗牌算法学习笔记数组随机排序洗牌算法给数组随机排序洗牌算法原理

原理及步骤

1.定义一个数组（shuffled），长度（length）是原数组（arr）长度
2.取 0 到 index (初始0) 随机值 rand, shuffled[index] = shuffled[rand], shuffled[rand] = arr[index]
3.index++ ; 重复第二步，直到 index = length -1
简单来说，就是 shuffled 从 0 到 length-1 的赋值过程，并且新加入的值是 arr[index]。

代码实现 1.代码一

function random(min, max) {
    if (max == null) {
        max = min;
        min = 0;
    }
    return min + Math.floor(Math.random() * (max - min + 1));
};
function shuffle(arr) {
    var length = arr.length, shuffled = Array(length);
    for (var index = 0, rand; index < length; index++) {
        rand = random(0, index);
        if (rand !== index) shuffled[index] = shuffled[rand];
        shuffled[rand] = arr[index];
    }
    return shuffled;
}

测试用例：

var arr = ["dfewfew", 2, 3, 4, 5, 6, 7, "fdf"", { kdofkod, jiji, miojim }];
shuffle(arr);

console输出：

[3, "dfewfew", 7, 2, 4, Array(3), "fdf"", 5, 6]

其中， Array(3)：length:3
0:"kdofkod"
1:"jiji"
2:"miojim"

2.代码二

function shuffle(arr) {
    var i, j, temp;
    for (i = arr.length - 1; i > 0; i--) {
        j = Math.floor(Math.random() * (i + 1));
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    return arr;
};

测试用例：

var arr = ["dfewfew", 2, 3, 4, 5, 6, 7, "fdf"", { kdofkod, jiji, miojim }];
shuffle(arr);

console输出：

[7, 3, "dfewfew", "fdf"", Array(3), 4, 6, 2, 5]

其中， Array(3)：length:3
0:"kdofkod"
1:"jiji"
2:"miojim"

参考资料

Fisher–Yates shuffle 洗牌算法
JavaScript学习笔记：数组随机排序
洗牌算法：给数组随机排序
洗牌算法Fisher_Yates原理

GPU云服务器云服务器数组随机排序 php数组随机排序字符串排序数组排序算法随机洗牌

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/82264.html

也谈前端面试常见问题之『数组乱序』

摘要：看完部分的源码，首先迫不及待想跟大家分享的正是本文主题数组乱序。这是一道经典的前端面试题，给你一个数组，将其打乱，返回新的数组，即为数组乱序，也称为洗牌问题。关于数组乱序，正确的解法应该是，复杂度。前言终于可以开始 Collection Functions 部分了。可能有的童鞋是第一次看楼主的系列文章，这里再做下简单的介绍。楼主在阅读 underscore.js 源码的时候，学到...

tracy 2019-08-19 18:42 评论0 收藏0
Underscore 源码（三）随机洗牌算法

摘要：随机洗牌算法说实话，以前理解数组的排序，都是将数组按照一定的逻辑由大到小或者由小到大排序，我自己是没有碰到过随机打乱数组排序的问题。然后里用的是所谓的洗牌算法，很高效。总结又是三个知识点，分别是随机洗牌分组和函数的实现，没什么复杂的。这是第三篇关于 Underscore 的源码解读，最近一段时间学的东西很少，自己太忙了，一方面忙着找实习，晚上回去还要写毕业论文。毕业论文真的很忧伤，因...

silencezwm 2019-08-20 16:42 评论0 收藏0
洗牌算法

摘要：描述拷贝数组从扫描数组，选择一个随机数新数组的新数组的新数组的原始数组重复第步，直到末尾最终的新数组就是随机的参考三种洗牌算法洗牌算法 Fisher-Yates Shuffle Fisher–Yates 随机置乱算法，通俗说就是生成一个有限集合的随机排列。描述：写下从 1 到 N 的数字取一个从 1 到剩下的数字（包括这个数字）的随机数 k 从低位开始，得到第 k 个还没有被...

omgdog 2019-08-23 17:53 评论0 收藏0
JavaScript30秒，从入门到放弃之Array（五）

摘要：原文地址秒，从入门到放弃之五博客地址秒，从入门到放弃之五水平有限，欢迎批评指正从给定的数组中随机选出指定个数的数组元素。否则判断数组元素是否大于或者等于指定元素，寻找过程与前边类似。原文地址：JavaScript30秒，从入门到放弃之Array（五）博客地址：JavaScript30秒，从入门到放弃之Array（五）水平有限，欢迎批评指正 sampleSize Gets n...

dunizb 2019-08-26 11:41 评论0 收藏0
JavaScript专题之乱序

摘要：源码地址为了简化篇幅，我们对这个数组进行分析，数组长度为，此时采用的是插入排序。插入排序的源码是其原理在于将第一个元素视为有序序列，遍历数组，将之后的元素依次插入这个构建的有序序列中。 JavaScript 专题系列第十九篇，讲解数组乱序，重点探究 Math.random() 为什么不能真正的乱序？乱序乱序的意思就是将数组打乱。嗯，没有了，直接看代码吧。 Math.random ...

I_Am 2019-08-21 17:00 评论0 收藏0