數組元素隨機化排序算法實現

做活動的時候(閃燈效果),經常會使用到數組隨機化.通俗名叫洗牌(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