JavaScript随机打乱数组顺序之随机洗牌算法
假如有一个数组是这样子:
vararr1=["a","b","c","d"];
如何随机打乱数组顺序,也即洗牌。
有一个比较广为传播的简单随机算法:
functionRandomSort(a,b){return(0.5-Math.random());}
实际证明上面这个并不完全随机。
随便一搜网上太多这种东西了,看一下stackoverflow上的一个高分回答,答案出自github上。
knuth-shuffle
TheFisher-Yates(akaKnuth)shuffleforBrowserandNode.JS
下面一起看看上面说的这个算法,代码如下:
/*jshint-W054*/ (function(exports){ 'usestrict'; //http://stackoverflow.com/questions/2450954/how-to-randomize-shuffle-a-javascript-array functionshuffle(array){ varcurrentIndex=array.length ,temporaryValue ,randomIndex ; //Whilethereremainelementstoshuffle... while(0!==currentIndex){ //Pickaremainingelement... randomIndex=Math.floor(Math.random()*currentIndex); currentIndex-=1; //Andswapitwiththecurrentelement. temporaryValue=array[currentIndex]; array[currentIndex]=array[randomIndex]; array[randomIndex]=temporaryValue; } returnarray; } exports.knuthShuffle=shuffle; }('undefined'!==typeofexports&&exports||'undefined'!==typeofwindow&&window||global));
作者推荐使用浏览器写法:
(function(){ 'usestrict'; vara=[2,11,37,42] ,b ; //Theshufflemodifiestheoriginalarray //callinga.slice(0)createsacopy,whichisassignedtob b=window.knuthShuffle(a.slice(0)); console.log(b); }());
Nodejs:
npminstall-Sknuth-shuffle (function(){ 'usestrict'; varshuffle=require('knuth-shuffle').knuthShuffle ,a=[2,11,37,42] ,b ; //Theshufflemodifiestheoriginalarray //callinga.slice(0)createsacopy,whichisassignedtob b=shuffle(a.slice(0)); console.log(b); }());
还有其它从这个算法中变形去的,比如下面这个for循环的。其它的就不说了。
/** *Randomizearrayelementorderin-place. *UsingDurstenfeldshufflealgorithm. */ functionshuffleArray(array){ for(vari=array.length-1;i>0;i--){ varj=Math.floor(Math.random()*(i+1)); vartemp=array[i]; array[i]=array[j]; array[j]=temp; } returnarray; }
使用ES2015(ES6)
Array.prototype.shuffle=function(){ letm=this.length,i; while(m){ i=(Math.random()*m--)>>>0; [this[m],this[i]]=[this[i],this[m]] } returnthis; }
使用:
[1,2,3,4,5,6,7].shuffle();
发现中文搜索随机算法一大堆,但究竟是不是完全随机,效率和兼容性都有待考究,建议后面如果有需要用到随机打乱数组元素,可以用上面这个。