在做拍拍首页改版过程碰到一个需求,抽象出来的意思就是:从一个数组当中随机抽出几个组成一个新的数组,然后思考了一下,代码如下():

// 判断数组是否包含某个元素
Array.prototype.contains = function(obj) {
var i = this.length;
while (i--) {
if (this[i] === obj) {
return true;
}
}
return false;
};
// 在min和max之间随机生成一个数字
var randomNum = function (min, max) {
if (max == undefined) {
max = min;
min = 0;
}
return Math.floor(Math.random() * (max - min) + min);
};
function shuffle (obj, arrLen) {
var randomArr = [],
$obj = obj,
len = $obj.length + 1;
while ( randomArr.length < arrLen ) {
var num = randomNum (len);
if ( randomArr.contains(num) ) {
continue;
}
randomArr.push(num);
}
return randomArr;
}

写完之后,虽然功能实现了,但是发现代码有点多而且逻辑有点复杂,我考虑的是从数组中随机抽出一个元素放入一个新的数组,只要新的数组的个数未到达指定个数,就不断循环从原数组中取元素,同时不能取出跟新数组重复元素,这样一来时间复杂度相对较高。

回到正题,doodle了一下,发现原来这个可以用传说中的洗牌算法来实现,基本原理是:从所有元素中随机选取一个与第一个元素进行交换,然后在第二个之后选择一个元素与第二个交换,直到最后一个元素。这样能确保每个元素在每个位置的概率都是1/n。

于是改进算法,代码如下:

//生成从1到length之间的随机数组
function shuffleArray ( len ) {
var arr = [], temp, index, i ;
if ( !len ) {
return false;
}
for ( i = 1; i <= len; i++) {
arr.push(i-1);
}
//利用洗牌算法打乱数组
for ( i = 1; i <= len; i++ ) {
//随机生成i到len之间的随机数
index = parseInt(Math.random() * ( len - i ), 10) + i;
if ( index != i ) {
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}
return arr;
}

思考继续改进中…