推荐高效的数组重排算法

文章类别：Flash AS编程 | 发表日期:2008-10-6 18:07:14

在程序设计中很多时候我们需要对数组重排，所以探求一种高效的重排算法还是很有必要的。上午逛论坛时看到一个帖子中的“简洁、高效”的重排算法，如下： 仅仅4行代码，当时我那个惭愧啊，自己以前怎么没有想到这么简单的方法了？还绕了一个大圈子来写这个重排。激动之后做了个测试：

function randomsort() { return Math.random()>.5 ? -1 : 1; } function arrRandomSort(arr){ arr.sort(randomsort); } _array = []; for (i = 0;i<1000;i++){ _array.push(Math.random()); } arr = []; var t1 = getTimer(); arr = arrRandomSort(_array); var t2=getTimer(); trace(t2-t1);

使用上面的算法对一个1000个元素的数组进行重排，执行时间是居然是210毫秒，有些恐怖，初步估计是因为sort函数造成的，因此将上面代码里添加了一个计数器来跟踪sort参数中的函数的执行次数。

_global.n = 1; function randomsort() { n++; return 1; } function arrRandomSort(arr){ arr.sort(randomsort); } _array = []; for (i = 0;i<1000;i++){ _array.push(Math.random()); } arr = []; var t1 = getTimer(); arr = arrRandomSort(_array); var t2=getTimer(); trace(t2-t1); trace(n);

    看来效率的消耗果然是因为sort函数，对这1000个元素的数组进行排序，运行了7153毫秒，randomsort函数被执行了499501次，显然，这段看似简洁的代码其实并不实用。而sort函数内部到底是使用什么算法来完成的这个排序了？以至于需要执行这么多次比较函数。简单排序？快速排序？我也不太清楚，有空了再做进深入测试，暂且不在此文讨论范围之内。
　　在我搜索Array.sort的内部实现时发现了一个帖子《用array.sort进行随机排序》，原来有关于用sort方法排序已经引起了很大的争议，而此文作者是站在支持sort排序的立场的，通过与别人的代码比较，他最初得出的结论是Array.sort来做数组重排是有利的，而跟帖中又出现了一个更为高效的算法，此算法跟sort方法相比效率要高很多，特推荐出来供大家借鉴。下面是我用此算法和sort算法做的对比，分别对100个元素的数组进行100次重排，比较其总消耗的时间，结果消耗时间分别为70MS和1448MS，其中红色部分为效率更佳算法：

/*算法一 */ Array.prototype.random = function($lim:Number):Array { var tmp:Array = this.concat(); var len:Number = tmp.length; //trace(($lim && $lim<(len-1)) ? $lim : (len-1)); for (var i = 0; i<(($lim && $lim<(len-1)) ? $lim : (len-1)); i++) { //获取最末索引 var n:Number = len-i; //索引集合中随机一个 var r:Number = random(n); //将选出来的元素放置到数组后面，以保证不在随机范围之内 var temp = tmp[r]; tmp[r] = tmp[n-1]; tmp[n-1] = temp; } return tmp.slice(-$lim); };  /*算法二*/ function getRandom() { return Math.random()<0.5 ? 1 : -1; } function arrayRandom(arr) { arr.sort(getRandom); return arr; } //--------------------------------------------------- //测试次数 var times = 100; //生成测试数据 var _array = []; for (var i = 0; i<100; i++) { _array.push(i); } //算法一: var t1 = getTimer(); for (i=0; i<TIMES; i++) { var arr = new Array(); arr = _array.random(); } //trace(arr); var t2 = getTimer(); trace("算法一耗时:"+(t2-t1)+"MS"); //算法二： var t1 = getTimer(); for (i=0; i<TIMES; i++) { var arr = new Array(); arr = arrayRandom(_array); } //trace(arr); var t2 = getTimer(); trace("算法二耗时:"+(t2-t1)+"MS"); //Result //算法一耗时:70MS //算法二耗时:1448MS

    实现原理并不复杂，首先将要重排的数组复制一份来操作，虽然效率上有点消耗但还是值得的，这样保证了原数组的不变动。然后很巧妙地将数组“分为”两个部分，每次从数组左边部分随机取出一个元素，然后将该元素交换到右部分的首元素，而分界线从数组末端往顶端移动，这样就保证了选出来的元素不会再被选出来，对于有N个元素的数组只需要进行N次此类操作就可以实现了数组的重排。

上一篇：{应用}flash中用as实现图像像素混合 人气:2199
下一篇：{应用}动态柱状图表制作原理 人气:2423

Flash AS编程视频教程