JavaScript学习笔记：数组随机排序_html/css_WEB-ITnose

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

在这篇文章一起来学习如何完成上面这个示例的效果，以及一些有关于数组随机排序的相关知识。

在网上查了一下有关于数组随机排序的相关资料，都看到了 Math.random() 的身影。打开浏览器控制器，输入：

Math.random()

有关于JavaScript随机数相关介绍，可以阅读《 Math.random()随机数的二三事 》一文。

从图中可以看出 Math.random() 得到的是 0~1 之间的随机数。众所周知， sort() 可以调用一个函数做为参数，如果这个函数返回的值为 -1 表示数组中的 a 项排在 b 项前。如此一来，可以写一个随机函数，让 Math.random() 随机出来的数与 0.5 做为一个比较，如果大于 .5 就返回 -1 ( a 排在 b 前面)，反之返回 1 ( b 排在 a 前面):

function randomSort(a, b) {    return Math.random() > 0.5 ? -1 : 1;}

看个示例：

var arr = [1,2,3,4,5,6,7,8,9];arr.sort(randomSort);

这样一来，就可以实现文章开头的示例效果：

虽然前面的方法实现了数组的随机排序，但总感觉每个元素被派到新数组的位置不是随机的。就如前面的示例，数组 arr 中值为 1 的元素，它的原先键值为 0 ，随机排序后， 1 的键值要求上为 0-8 的几率是一样的。然后在这里是递减的，原因是 sort() 方法是依次比较的。

针对这种现象，我们可以使用下面这种递归的方法来处理：

function randomSort(arr, newArr) {    // 如果原数组arr的length值等于1时，原数组只有一个值，其键值为0    // 同时将这个值push到新数组newArr中    if(arr.length == 1) {        newArr.push(arr[0]);        return newArr; // 相当于递归退出    }    // 在原数组length基础上取出一个随机数    var random = Math.ceil(Math.random() * arr.length) - 1;    // 将原数组中的随机一个值push到新数组newArr中    newArr.push(arr[random]);    // 对应删除原数组arr的对应数组项    arr.splice(random,1);    return randomSort(arr, newArr);}

如此一来，我们就可以这样使用：

for (var i = 0; i < 10; i++) {    var arr=[1,2,3,4,5,6,7,8,9];    var newArr=[];    randomSort(arr,newArr);    console.log(newArr);}

输出结果：

执行 randomSort(arr,newArr) 函数之后，原数组 arr 就清空了。

如果使用这种方法来做文章开头洗牌的示例，就要在 resetPic() 函数中重置 pukePic 数组：

除了上面的两种方法之外， @Traveller 在 DIV.IO 分享了一篇《 数组元素随机化排序算法实现 》，这篇文章提供了三种数组项随机排序的实现方法：

使用数组sort方法对数组元素随机排序

Array.prototype.shuffle = function(n) {    var len = this.length ,        num = n ? Math.min(n,len) : len,        arr = this.slice(0);    arr.sort(function(a,b){        return Math.random()-0.5;    });    return arr.slice(0,num-1);}

随机交换数组内的元素

lib = {}lib.range = function(min,max) {    return min + Math.floor(Math.random()*(max-min+1));}Array.prototype.shuffle = function(n) {    var len = this.length,        num = n ? Math.min(n,len) : len,        arr = this.slice(0),        temp,        index;    for (var i=0;i<len;i++){        index = lib.range(i,len-1);        temp = arr[i];        arr[i] = arr[index];        arr[index]=temp;    }    return arr.slice(0,num);}

随机从原数组抽取一个元素,加入到新数组

lib = {}lib.range = function(min,max) {    return min+Math.floor(Math.random()*(max-min+1));}Array.prototype.shuffle = function(n) {    var len = this.length,         num = n ? Math.min(n,len) : len,        arr = this.slice(0),        result=[],        index;    for (var i=0;i<num;i++){        index = lib.range(0,len-1-i);        // 或者 result.concat(arr.splice(index,1))        result.push(arr.splice(index,1)[0]);  }  return result}

洗牌算法

数组随机排序其基本原理是洗牌算法(Fisher–Yates shuffle)：

是一种将有限集合的顺序打乱的一种算法

原理

• 定义一个数组（ shuffled ），长度（ length ）是原数组（ arr ）长度
• 取 0 到 index (初始 0 ) 随机值 rand , shuffled[index] = shuffled[rand] , shuffled[rand] = arr[index]
• index++ ; 重复第二步，直到 index = length -1

就是 shuffled 从 0 到 length-1 的赋值过程，并且新加入的值是 arr[index] ， shuffled[index] 的值是已赋值的元素中随机值 shuffled[rand] ，因为这样会有两个重复的值，所以 shuffled[rand] 就等于新加入的值 arr[index]

underscore.js 中的 shuffle 方法

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 = [1,2,3,4,5,6,7,8,9];for (var i = 0; i < 10; i++){    console.log(shuffle(arr));}

Chrome输出的结果如下：

同样的，使用洗牌算法来完成文章最开头的示例：

还有更简单易理解的写法：

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;};

有关于洗牌算法扩展阅读

• Fisher–Yates shuffle
• Shuffling an Array in JavaScript
• Fisher–Yates Shuffle
• 如何测试洗牌程序
• Fisher-Yates-shuffle洗牌算法
• How to randomize (shuffle) a JavaScript array?

总结

这篇文章主要总结和收集了有关于数组随机排序我相关资料。当然在坊间实现类似功能的方法还有很多种，此处只是收集和整理了这些，如果你有更好的方法，欢迎在评论中与我们一起分享。

初学者学习笔记，如有不对，还希望高手指点。如有造成误解，还希望多多谅解。

大漠

常用昵称“大漠”，W3CPlus创始人，目前就职于手淘。中国Drupal社区核心成员之一。对HTML5、CSS3和Sass等前端脚本语言有非常深入的认识和丰富的实践经验，尤其专注对CSS3的研究，是国内最早研究和使用CSS3技术的一批人。CSS3、Sass和Drupal中国布道者。2014年出版《 图解CSS3：核心技术与案例实战 》。