[转] as3实现快速排序
http://bbs.9ria.com/viewthread.php?tid=77114&extra=page%3D1%26amp%3Borderby%3Ddateline%26amp%3Bfilter%3D2592000
呵呵，这是俺第一次操刀写技术性的文章，有错的地方大家就指出来
快排思想：
通过一趟排序将要排序的东东分成独立的2部分，
这样的结果是一部分的数据比另外一部分的所以数据都要小，
接着对这两部分数据分别进行快速排序（这个过程有很多种方法，我这里用的是递归），
之后要排序的东东就排好了。
代码实现：
package{ import flash.display.Sprite; public class Main extends Sprite {// var arr:Array = [5,1,4,3,10,0,46]; var arr:Array = [49,38, 65, 97, 76, 13, 27 ]; public function Main() { getArr(); var timeStart:Number = (new Date()).getTime(); trace("排序前："+arr); // bubbleSort();//3766ms quickSort(0,arr.length-1);//31ms trace("排序后："+arr); var timeEnd:Number = (new Date()).getTime(); trace('排序用时：'+(timeEnd-timeStart)); } private function getArr():void{ for(var i:int=0;i<5000;i++){ arr[i] = int(Math.random()*100); } } private function bubbleSort():void{ for(var i:int=0;i<arr.length-1;i++){ for(var j:int=arr.length-1;j>i;j--){ if(arr[j]<arr[j-1]){ var temp:int = arr[j-1]; arr[j-1] = arr[j]; arr[j] = temp; } } } } private function quickSort(start:int,end:int):void{ if(start<0||end>arr.length){ trace('参数不合法'); return; } if(start<end){ var i:int = start; var j:int = end; var base:int = arr[start]; while(i<j){ while(i<j&&arr[j]>=base) j--; if(i<j) { arr[i] = arr[j]; i++; } while(i<j&&arr[i]<=base) i++; if(i<j){ arr[j] = arr[i]; j--; } } arr[i] = base; quickSort(start,i-1); quickSort(i+1,end); } } }}private function quickSort(start:int,end:int):void{ if(start<0||end>arr.length){ trace('参数不合法'); return; } if(start<end){ //递归出口，很重要，组成递归的条件之一 //用i,j模拟指针扫描数组，i向后，j向前 var i:int = start; var j:int = end; //找个基准点，随便选的 var base:int = arr[start]; //第一次排序开始,经过此次排序后将会把数组分成两部分（当然不是分成2个数组了，就是那么个意思） while(i<j){ //大于或等于基准点的移动指针j while(i<j&&arr[j]>=base) j--; //移动指针j时，碰到小于基准点的数，且满足i<j，把它朝前扔，至于为什么要i++呢，因为while(i<j)这个循环时可能还会满足以下情况要朝前扔 if(i<j) { arr[i] = arr[j]; i++; } while(i<j&&arr[i]<=base) i++; if(i<j){ arr[j] = arr[i]; j--; } } //把基准点的值赋给数组i位置的值 arr[i] = base; //第一次排序结束，你会发现基准点前面的数全部比它小，基准点后面的数全部比它大 //递归排列基准点前面的数 quickSort(start,i-1); //递归排列基准点后面的数 quickSort(i+1,end); } }