在做拍拍首页改版过程碰到一个需求,抽象出来的意思就是:从一个数组当中随机抽出几个组成一个新的数组,然后思考了一下,代码如下():
Array.prototype.contains = function(obj) { var i = this.length; while (i--) { if (this[i] === obj) { return true; } } return false; }; 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。
于是改进算法,代码如下:
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++ ) { index = parseInt(Math.random() * ( len - i ), 10) + i; if ( index != i ) { temp = arr[i]; arr[i] = arr[index]; arr[index] = temp; } } return arr; }
|
思考继续改进中…