·您当前的位置:首页 > 技术教程 > AS2与AS3技术 >

[AS3]基于AS3做的随机排序源代码

时间:2016-03-08 13:55酷播
[AS3]基于AS3做的随机排序源代码,sort可以带一个比较函数,排序时,会自动匹配所有两个参数进行比较

算法列表:
1.自身插入法

  1. private function randomArr(arr:Array):Array 
  2. var outputArr:Array = arr.slice(); 
  3. var i:int = outputArr.length; 
  4.  
  5. while (i) 
  6. outputArr.push(outputArr.splice(int(Math.random() * i--), 1)); 
  7. return outputArr; 

通常插入法是将随机移出来的数扔到新的数组里,但是这么写的牛逼之处在于扔自己数组后面了,大大节省了效率:);

2.选择法(已经修正)

  1. private function randomArr(arr:Array):Array 
  2. var outputArr:Array = arr.slice(); 
  3. var i:int = outputArr.length; 
  4. var temp:*; 
  5. var indexA:int; 
  6. var indexB:int; 
  7.  
  8. while (i) 
  9. iindexA = i-1; 
  10. indexB = Math.floor(Math.random() * i); 
  11. i--; 
  12. if (indexA == indexB) continue; 
  13. temp = outputArr[indexA]; 
  14. outputArr[indexA] = outputArr[indexB]; 
  15. outputArr[indexB] = temp; 
  16.  
  17. return outputArr; 

选 择排序法就是按照顺序从余下数中选出最小(大)的数,和顺序位置的数字交换,反复进行。此法最多可能会交换n-1次,比如[4,1,2,3]递增排序中的 4就需要挪3次,当然最少一次也不用。但是随机算法循环次数无法浮动,必须是固定的,怎么办呢?没有关系,我们可以引入废操作,位置已经摆对的数自己和自 己交换,这样就可以让所有顺序排序都成为n-1步走。
反过来想就明白了,从0开始每个位置和后面的随机位置交换,也可以和自己交换,直到n-2和n-1(或n-2自己交换),就可以得到一个随机数组。


3.利用Sort() (具体原理不明)

  1. private function randomArr5(arr:Array):Array 
  2. var outputArr:Array = arr.slice(); 
  3. outputArr.sort(function():int{return Math.random()>.5?1:-1});  
  4. return outputArr; 

sort可以带一个比较函数,排序时,会自动匹配所有两个参数进行比较,

当返回值为1时,参数A对应元素排到参数B对应元素后

当返回值为0时,参数A与参数B位置保持不变

当返回值为-1时,参数B对应元素排到参数A对应元素前

 



效率比较:

利用1-100的顺序数组进行测试,执行10000次所用的时间分别为。
自身插入法:1654
普通插入法(放进新数组): 2574
选择法: 499594
利用Sort() :1479
选择法>Sort() >自身插入法

http://bbs.9ria.com/thread-158112-1-1.html

热门文章推荐

请稍候...

保利威视云平台-轻松实现点播直播视频应用

酷播云数据统计分析跨平台播放器