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

推荐阅读:JavaScript学习笔记之数组的增、删、改、查

JavaScript学习笔记之数组求和方法

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

洗牌算法是一个比较形象的术语,本质上让一个数组内的元素随机排列。举例来说,我们有一个如下图所示的数组,数组长度为 9,数组内元素的值顺次分别是 1~9:

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

代码实现

维基百科上的 Fisher–Yates shuffle 词条对洗牌算法做了详细介绍,下面演示的算法也是基于其中的理论编写的:

Array.prototype.shuffle = function() {
var input = this;
for (var i = input.length-1; i >=0; i--) {
var randomIndex = Math.floor(Math.random()*(i+1));
var itemAtIndex = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIndex;
}
return input;
}
var tempArray = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
tempArray.shuffle();
// and the result is...
alert(tempArray); 

在上面的代码中,我们创建了一个 shffle() 方法,该方法用于随机排列数组内的元素。此外,我们将该方法挂载在了 Array 对象的原型下面,所以任何数组都可以直接调用该方法:

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

工作原理

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

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

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

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

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

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

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

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

分析代码

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

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

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

var input = this;

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

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

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

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

洗牌算法

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

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

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

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

var itemAtIndex = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIndex;

在这三行代码中,第一行使用新的变量保存了随机元素的值;第二行将选中元素 input[i] 的值赋给随机元素 input[randomIndex];第三行就随机元素的值 itemAtIndex 赋给选中元素 input[i]。本质上是一个互换两个元素的值的过程,并不难理解。

至此,循环内的逻辑就介绍完了,剩下的都是重复操作。

随机性测试

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

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

由计算可得:

以上内容是小编给大家介绍的JS随机洗牌算法之给数组随机排序的相关叙述,希望对大家有所帮助!

(0)

相关推荐

  • 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函数

  • 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随机打乱数组顺序之随机洗牌算法

    假如有一个数组是这样子: var arr1 = ["a", "b", "c", "d"]; 如何随机打乱数组顺序,也即洗牌. 有一个比较广为传播的简单随机算法: function RandomSort (a,b){ return (0.5 - Math.random()); } 实际证明上面这个并不完全随机. 随便一搜网上太多这种东西了,看一下stackoverflow上的一个高分回答,答案出自github上. knuth-s

  • JS随机打乱数组的方法小结

    本文实例总结了JS随机打乱数组的方法.分享给大家供大家参考,具体如下: JS中,要打乱数组有很多方法,网上流传一个国外人写的方法,我认为是最精简的了: function randomsort(a, b) { return Math.random()>.5 ? -1 : 1; //用Math.random()函数生成0~1之间的随机数与0.5比较,返回-1或1 } var arr = [1, 2, 3, 4, 5]; arr.sort(randomsort); 这里介绍下sort()函数,在JS中

  • js获取数组任意个不重复的随机数组元素 原创

    复制代码 代码如下: <script language="javascript"> //从一个给定的数组arr中,随机返回num个不重复项 function getArrayItems(arr, num) { //新建一个数组,将传入的数组复制过来,用于运算,而不要直接操作传入的数组; var temp_array = new Array(); for (var index in arr) { temp_array.push(arr[index]); } //取出的数值项,

  • JS 在指定数组中随机取出N个不重复的数据

    复制代码 代码如下: <script language="javascript">//从一个给定的数组arr中,随机返回num个不重复项function getArrayItems(arr, num) {    //新建一个数组,将传入的数组复制过来,用于运算,而不要直接操作传入的数组;    var temp_array = new Array();    for (var index in arr) {        temp_array.push(arr[index]

  • 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

  • js实现从数组里随机获取元素

    基础知识: 复制数组: (1)循环遍历复制(不推荐) 复制代码 代码如下: var arry = [1,5,9,7],     new_arry = [],     n = 0,     len = arry.length; for(;n<len;n++){     new_arry.push(arry[n]); } (2)concat() 方法用于连接两个或多个数组,该方法不会改变现有的数组,而仅仅会返回被连接数组的一个副本 复制代码 代码如下: var arry = [1,5,9,7],  

  • JS从数组中随机取出几个数组元素的方法

    JS如何从一个数组中随机取出一个元素或者几个元素. 假如数组为 var items = ['1','2','4','5','6','7','8','9','10']; 1.从数组items中随机取出一个元素 var item = items[Math.floor(Math.random()*items.length)]; 2.从前面的一篇随机数组中随机取几个元素 function getRandomArrayElements(arr, count) { var shuffled = arr.sl

  • JavaScript数组随机排列实现随机洗牌功能

    本文实例讲述了JavaScript数组随机排列实现随机洗牌功能的方法.分享给大家供大家参考.具体分析如下: 这段JS代码可以对数组内的元素进行随机排列,这个非常有用,比如我们在玩扑克牌的时候可以让扑克牌进行排列,也就是电脑洗牌. var list = [1,2,3,4,5,6,7,8,9]; list = list.sort(function() Math.random() - 0.5); Print(list); // prints something like: 4,3,1,2,9,5,6,

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

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

随机推荐