内容简介:javascript如何将一个无序的数组变成一个有序的数组,我们有很多的排序算法可以实现,例如冒泡算法,快速排序,插入排序等。然而我们是否想过,如何将一个有序的数组乱序输出呢?本文将从经典的洗牌算法出发,详细讲解underscore中关于乱序排列的实现。在介绍洗牌算法的概念前,我们先引入现实生活的一个经典例子。当我们和多人一起玩扑克牌的时候,我们需要先将一份全新的扑克牌打乱,让牌组随机化,以确保游戏的公平性。这个将牌组随机化的过程,我们衍生到代码中可以概括为: 一个有序的数组[1,2,3,4,5],如何随机
javascript如何将一个无序的数组变成一个有序的数组,我们有很多的 排序 算法可以实现,例如冒泡算法,快速排序,插入排序等。然而我们是否想过,如何将一个有序的数组乱序输出呢?本文将从经典的洗牌算法出发,详细讲解underscore中关于乱序排列的实现。
六,洗牌算法
6.1 问题探讨
在介绍洗牌算法的概念前,我们先引入现实生活的一个经典例子。当我们和多人一起玩扑克牌的时候,我们需要先将一份全新的扑克牌打乱,让牌组随机化,以确保游戏的公平性。这个将牌组随机化的过程,我们衍生到代码中可以概括为: 一个有序的数组[1,2,3,4,5],如何随机打乱,使生成一个随机的数组,如[3,2,5,1,4],且需要保证数组中的数出现在每个位置的概率相同。如何实现呢?
利用es5的sort函数,其实我们很容易找到一种简洁的方法。
var shuffle = (arr) => arr.sort(() => Math.random() - 0.5) 复制代码
本质上利用es6原生的sort函数,我们可以达到数组乱序,然而sort方法本身却无法保证元素出现在每个位置上出现的概率随机。在 关于 JavaScript 的数组随机排序 一文中,作者详细讲解了使用sort排序并不能保证随机,并且列举了造成无法随机化的原因。文章较长,大概可以总结为以下两点。
- 1.各个浏览器对于sort中使用 排序算法 的差异导致sort本身随机排序概率的差异,例如chrome浏览器对排序算法做了优化,小于等于10的数组使用相对稳定的插入排序,大于10的采用相对不稳定的快速排序,而FireFox使用的排序算法是归并排序等。显然,排序算法的不同,导致使用sort排序的概率结果也不可能相同。
- 2.sort排序的本质还是两两比较,而我们知道,一个n位数组,要进行两两比较,它的时间复杂度为n(n-1)/2, 而不管什么排序算法,它的时间复杂度都要小于n(n-1)/2,那既然如此,又如何保证新数组已经是两两比较后生成的随机数组呢。
6.2 洗牌算法概念
其实,为了实现这一场景,前人已经给出了问题的答案,也就是公认成熟的洗牌算法(Fisher-Yates),简单的思路如下:
-
- 定义一个数组,以数组的最后一个元素为基准点。
-
- 在数组开始位置到基准点之间随机取一个位置,将所取位置上的元素和基准点上的元素互换。
-
- 基准点左移一位。
-
- 重复2,3步骤,直到基准点为数组的开始位置。
由于第二步生成随机位置的随机性,所以整个洗牌算法保证了乱序的随机性。将文字转化为代码,javascript的简单实现如下:
function shuffle(arr) { var length = arr.length, j = length; for (var i = 0; i < length; i++) { var random = Math.floor(Math.random() * (j--)); // 生成起始位置到基准位置之间的随机位置,并将基准从结束位置不停左移。 // es3实现 var newA = arr[i]; arr[i] = arr[random]; arr[random] = newA // es6 实现 [arr[i], arr[random]] = [arr[random], arr[i]]; // 本质为交换元素位置。 } return arr } 复制代码
underscore中在乱序方面同样用到了洗牌算法,有了洗牌算法的概念和实现基础后,接下来我们将关注点放在underscore中乱序方法的实现中。
6.3 random - _.random(min, max)
洗牌算法的第二步,生成随机数的过程,无疑需要使用到原生 Math.random()
(产生一个[0,1)之间的随机数),而underscore在原生的 Math.random()
方法上,重新包装了random函数,实现在给定范围内生成随机整数,如果只传递一个参数,那么将返回0和这个参数之间的整数。
// 随机函数 _.random = function (min, max) { if (max == null) { // max == null即代表只传递一个参数,此时最大值为传递的最小值,最小值为0 max = min; min = 0; } return min + Math.floor(Math.random() * (max - min + 1)); // 生成[min, max]之前的随机数 }; 复制代码
6.4 sample - _.sample(list, [n])
在underscore 1.8版本以前,洗牌算法的实现直接放在了 _.shuffle 方法中实现,而1.9的版本直接抛弃了这种写法,我们将放在下文分析这种写法。在1.9版本中,洗牌算法的实现放在了sample函数中,sample会在 list中产生一个随机样本。n则代表返回多少个随机数。同时list不仅可以是数组,也可以是对象或者类数组,当list为对象时,随机返回的是对象的值,如
console.log(_.sample({a: 123, b: 234}, 2)) // 234 123 复制代码
实现思路如下
_.sample = function(list, n) { if(n == null) { // 不指定个数时,默认在数组中随机取出一个。 if (!isArrayLike(obj)) list = _.values(list); // list为对象时,取出对象值的集合。 return list[_.random(list.length - 1)] // 生成数组的随机位置,返回该位置的值。 } var sample = isArrayLike(obj) ? _.clone(obj) : _.values(obj); // 数组类数组得到克隆的数组,对象得到值的集合。 var length = getLength(sample); n = Math.max(Math.min(n, length), 0); // 对n的大小做限制,不能大于新数组的长度,不能小于0。 var last = length - 1; for (var index = 0; index < n; index++) { // for循环下的操作为洗牌算法的核心步骤,和前面讲解的实现方式相同。 var rand = _.random(index, last); var temp = sample[index]; sample[index] = sample[rand]; sample[rand] = temp; } return sample.slice(0, n); } 复制代码
6.5 shuffle - _.shuffle(list)
shuffle是洗牌算法的用法函数,返回一个随机乱序的list副本。有了_.sample的基础,shuffle只需要传递一个n值为数组长度的参数给sample函数即可。
_.shuffle = function(list) { return _.sample(obj, Infinity); // n值传递无穷大,由于sample函数内部对n值的限制,真正执行洗牌算法时,n的值为数组的长度。 } 复制代码
6.6 underscore其他版本的实现
前面提到,1.8版本以前underscore对于洗牌算法的实现放在了shuffle函数中,它的实现相比于1.9版本来说,有很多的巧妙之处,我们来看看实现代码。
_.shuffle = function(obj) { var set = obj && obj.length === +obj.length ? obj : _.values(obj); var length = set.length; var shuffled = Array(length); for (var index = 0, rand; index < length; index++) { rand = _.random(0, index); if (rand !== index) shuffled[index] = shuffled[rand]; shuffled[rand] = set[index]; } return shuffled; }; 复制代码
// 交换位置代码 if (rand !== index) shuffled[index] = shuffled[rand]; shuffled[rand] = set[index]; 复制代码
中间关系乱序的实现看起来很巧妙,我们来详细分析每一步是如何进行的。
-
我们定义一个数组
[1,2,3,4]
-
生成一个长度相同的空数组作为乱序后的新数组
shuffle = [undefined, undefined, undefined, undefined]
- index从第一个数开始,也就0开始,生成一个 0 - index 之间的随机数,第一个固定为0
-
随机数和 index相同,所以执行
shuffled[0] = set[0] = 1
shuffle依然为shuffle = [1, undefined, undefined, undefined]
- index = 1, 生成 0 -1 之间的随机数,假设随机数为0
-
此时执行交换代码
shuffled[1] = shuffled[0] = 1 ; shuffled[0] = set[1] = 2;
即 shuffle改变成shuffle = [2, 1, undefined, undefined]
- index = 2, 生成 0 - 2 之间的随机数,假设随机数为1
-
此时执行交换代码
shuffled[2] = shuffled[1] = 1 ; shuffled[1] = set[2] = 3;
即 shuffle改变成shuffle = [2, 3, 1, undefined]
- index = 3, 生成 0 - 3 之间的随机数,假设随机数为0
-
此时执行交换代码
shuffled[3] = shuffled[0] = 3 ; shuffled[0] = set[3] = 4;
即 shuffle改变成shuffle = [4, 3, 1, 2]
经过以上十步,乱序数组也随之生成
以上所述就是小编给大家介绍的《打造属于自己的underscore系列(六)- 洗牌算法》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 图解洗牌算法
- 洗牌算法及 random 中 shuffle 方法和 sample 方法浅析
- AS3.0 扑克牌乱序排列法洗牌
- 币圈大佬纷纷退出,币圈要重新洗牌还是从此散去?
- 通俗易懂--决策树算法、随机森林算法讲解(算法+案例)
- 限流算法之漏桶算法、令牌桶算法
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
UNIX环境高级编程
W.Richard Stevens、Stephen A.Rago / 尤晋元、张亚英、戚正伟 / 人民邮电出版社 / 2006年 / 99.00元
本书是被誉为UNIX编程“圣经”的Advanced Programming in the UNIX Environment一书的更新版。在本书第1版出版后的十几年中,UNIX行业已经有了巨大的变化,特别是影响UNIX编程接口的有关标准变化很大。本书在保持了前一版风格的基础上,根据最新的标准对内容进行了修订和增补,反映了最新的技术发展。书中除了介绍UNIX文件和目录、标准I/O库、系统数据文件和信息......一起来看看 《UNIX环境高级编程》 这本书的介绍吧!