[转] RPG游戏中深度排序性能比较.

http://bbs.9ria.com/viewthread.php?tid=73161&extra=page%3D1%26amp;orderby%3Ddateline%26amp;filter%3D86400

以下是我在做MMORPG初期的时候，进行的一些算法性能测试，今天在整理东西的时候不小心看到了，所以把他给分享给大家，RPG游戏中经常用的深度排序方法，我将大家常用的方法做了很小的修改进行性能测试,
结果如下:
性能从高到低:doSort4,doSort1,doSort3,doSort2,doSrot5
doSort1:先数组的sortOn排序,再用setChildIndex设置层.
doSort2:先数组的sortOn排序,再用swapChildren设置层,不设置没有变化的层.
doSort3:先数组的sortOn排序,再用swapChildrenAt设置层,不设置没有变化的层.
doSort4:先数组的sortOn排序,再用setChildIndex设置层,不设置没有变化的层.
doSort5:这里我是采用分冶策略和快速排序的思想是一样的，我原以为这种方法会很快，结果不是这样的，这里不是因为分冶策略的方法慢，是因为每次划分的时候都会带来错误的层设置，所以导致最终的速度变慢,大家可以将doSort4结合4叉树进行深度排序
               

           private function doSort1(maxNum:int):void {
                        var sortedLayers:Array = arrayResult;
                        sortedLayers.sortOn("y",Array.NUMERIC)
                        var item:Sprite=null;
                        var child:Sprite=null;
                        for (var i:uint=0; i<maxNum; i++) {
                                setNum++;
                                setChildIndex(sortedLayers[i], i);// 最耗cpu
                        }
           }
        private function doSort2(maxNum:int):void {
                        var sortedLayers:Array = arrayResult;
                        sortedLayers.sortOn("y",Array.NUMERIC)
                        var item:Sprite=null;
                        var child:Sprite=null;
                        for (var i:uint=0; i<maxNum; i++) {
                                item = sortedLayers[i];
                                child = getChildAt(i) as Sprite;
                                if (child != item) {
                                        setNum++
                                        swapChildren(child, item);
                                }
                        }
       }
      private function doSort3(maxNum:int):void {
                var sortedLayers:Array = arrayResult;
                sortedLayers.sortOn("y",Array.NUMERIC)
                var item:Sprite=null;
                var child:Sprite=null;
                for (var i:uint=0; i<maxNum; i++) {
                        item = sortedLayers[i];
                        child = getChildAt(i) as Sprite;
                        if (child != item) {
                                setNum++
                                swapChildrenAt(i, getChildIndex(item));
                                        
                        }
                }
     }
      private function doSort4(maxNum:int):void {
                var sortedLayers:Array=arrayResult;
                sortedLayers.sortOn("y",Array.NUMERIC)
                var item:Sprite=null;
                var child:Sprite=null;
                while (maxNum--) {
                        item = sortedLayers[maxNum];
                        child = getChildAt(maxNum) as Sprite;
                        if (child != item) {
                                setNum++
                                setChildIndex(sortedLayers[maxNum], maxNum);
                        }
                }
        }
                //公冶策略
         public  function doSort5(array:DisplayObjectContainer):void{
                var size:uint=array.numChildren;
                sort(0,size-1);
                function sort(left:int,right:int):void{
                        if(left>=right) return;
                        var mid:int=getPartition(left,right,array.getChildAt(right));   
                        sort(left,mid-1);
                        sort(mid+1,right);
                }
                        
                function getPartition(left:int,right:int,mid:DisplayObject):int{
                        var lp:int=left-1;
                        var rp:int=right;
                        while(true){
                                while(mid.y>array.getChildAt(++lp).y){}
                                while(rp>0 && array.getChildAt(--rp).y>mid.y){}
                                if(lp>=rp){
                                        break;
                                else{
                                        array.swapChildrenAt(lp,rp)
                                }
                        }
                        array.swapChildrenAt(right,lp)
                        return lp;
                }
                        
          }

doSort5，是不是对数组进行快速排序，到最后再来一次setChildIndex要快一点呢。
在getPartition中每次都swapChildrenAt，不太好吧。
另外递归的掉用，应该也会影响点效率的吧


还是不如

			var sortedLayers:Array= _list;  
			var maxNum:int = sortedLayers.length;
			var t:int = getTimer();
			sortedLayers.sortOn("y",Array.NUMERIC);
			var item:Sprite=null;  
			var child:Sprite=null;  
			var numChilds:int = sp.numChildren;
			while (maxNum--) 
			{  
				item = sortedLayers[maxNum];
				sp.addChildAt(item, maxNum);
			}  

这样效率高