数组元素随机化排序算法实现详解编程语言

做活动的时候(闪灯效果),经常会使用到数组随机化.通俗名叫洗牌(shuffle)算法

方法一:使用数组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) 
} 

测试代码,输出 [1,2,3,4,5,6,7,8,9,10]排序后的20次结果,时间测试为1-299的数组,做10000次随机化的时间

var arr =[],t1,t2 
for(var i=1;i<300;i++) {arr.push(i)} 
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) 
} 
t1 = new Date 
 
  for (var i=0;i<10000;i++) { 
   // console.log(arr.shuffle().join())  
   arr.shuffle() 
  } 
t2 = new Date 
console.log(t2-t1) 

在firefox的console里跑20次结果:

1,2,3,4,5,6,9,8,7,10 
6,4,9,7,2,8,5,10,3,1 
9,3,10,8,1,7,2,5,6,4 
1,2,3,6,5,4,9,8,7,10 
2,1,3,5,4,6,8,9,7,10 
2,10,4,8,3,5,1,6,9,7 
5,6,4,1,2,3,8,10,7,9 
7,9,6,8,10,2,1,4,3,5 
3,2,9,8,1,7,10,4,5,6 
5,4,3,6,2,1,8,9,7,10 
7,8,9,10,3,1,2,6,4,5 
1,2,3,4,6,5,9,10,8,7 
1,9,10,3,2,6,5,8,4,7 
3,2,1,5,4,6,7,10,9,8 
1,2,3,5,4,6,8,10,7,9 
1,8,4,7,9,2,3,6,10,5 
9,2,1,3,4,8,7,5,6,10 
2,1,4,5,3,6,9,8,7,10 
4,6,10,8,9,2,7,1,5,3 
7,8,2,1,3,9,10,5,4,6 
3306ms 

可以看到此段代码对有序数组产生的随机效果不佳,易结块(一定区间的内容还是在一起).分析原理也不难得出产生此结果的原因

方法二:随机交换数组内的元素 (原理from underscore.js

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

测试结果 : 随机数还是比较理想的.

4,3,1,6,9,10,7,2,8,5 
4,9,3,10,7,1,6,2,8,5 
8,6,3,5,9,4,2,7,1,10 
9,6,1,5,8,3,10,7,2,4 
10,3,1,7,4,8,9,6,2,5 
9,6,7,2,1,4,10,3,5,8 
2,4,6,9,5,1,10,8,3,7 
7,3,9,8,1,6,5,2,10,4 
6,7,5,10,3,9,4,2,1,8 
2,4,3,8,1,9,6,7,5,10 
8,5,7,4,3,2,10,1,6,9 
9,7,1,2,3,4,10,5,6,8 
2,6,10,7,1,9,8,5,4,3 
1,6,8,2,4,7,10,5,9,3 
7,4,2,1,9,5,3,8,10,6 
5,3,9,8,2,10,6,1,4,7 
8,4,2,6,7,10,1,5,9,3 
7,2,4,3,9,1,5,8,10,6 
5,7,9,8,4,3,2,1,6,10 
4,6,5,7,1,9,3,10,2,8 
1576ms 

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

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.push(arr.splice(index,1)[0])        // or result.concat(arr.splice(index,1)) 
  } 
  return result 
 
} 

测试结果

1,9,2,4,6,8,10,5,3,7 
6,8,2,3,10,1,9,7,5,4 
2,5,9,4,10,3,8,6,7,1 
2,8,3,9,1,5,10,4,7,6 
8,4,10,9,3,6,5,2,7,1 
8,4,9,5,2,10,3,6,7,1 
9,2,3,8,1,6,10,4,7,5 
2,1,4,3,10,5,8,9,6,7 
3,10,4,7,6,1,2,9,5,8 
2,3,5,7,6,1,4,8,9,10 
4,3,5,9,7,2,6,10,8,1 
4,7,6,9,3,1,2,5,8,10 
3,4,1,5,6,10,9,7,8,2 
5,3,10,7,9,2,8,6,4,1 
2,4,5,10,1,7,6,8,9,3 
8,5,10,9,4,1,6,7,2,3 
4,5,3,6,10,7,1,8,9,2 
10,6,3,1,2,5,9,4,7,8 
2,3,4,5,10,6,9,8,1,7 
9,3,8,6,10,7,1,4,2,5 
2944ms 

GitHub Address: https://github.com/myheartwillgoon/FEDev/issues/2