预览加载中,请您耐心等待几秒...
1/5
2/5
3/5
4/5
5/5

在线预览结束,喜欢就下载吧,查找使用更方便

如果您无法下载资料,请参考说明:

1、部分资料下载需要金币,请确保您的账户上有足够的金币

2、已购买过的文档,再次下载不重复扣费

3、资料包下载后请先用软件解压,在使用对应软件打开

php如何实现快速排序php如何实现快速排序php实现快速排序的方法有三种,下面小编为大家介绍php如何实现快速排序吧,欢迎大家阅读!php如何实现快速排序方法一:该方法比较直观,但损失了大量的空间为代价,使用了效率较低的merge函数。在三种方法中效率最低。最坏情况下算法退化为(O(n*n))代码如下:functionquick_sort($array){if(count($array)<=1)return$array;$key=$array[0];$rightArray=array();$leftArray=array();for($i=1;$i<count($array);$i++){if($array[$i]>=$key){$rightArray[]=$array[$i];}else{$leftArray[]=$array[$i];}}$leftArray=quick_sort($leftArray);$rightArray=quick_sort($rightArray);returnarray_merge($leftArray,array($key),$rightArray);}方法二:该算法来自算法导论,叫作NicoLomuto方法(感兴趣goole上有详细说明)使用最经典的`单方向一次遍历找到中值。但这种算法在最坏情况下(例如值相同的数组,需要n-1次划分,每一次划分需要O(n)时间去掉一个元素)最坏情况下为O(n*n)代码如下:functionquick_sort(&$array,$start,$end){if($start>=$end)return;$mid=$start;for($i=$start+1;$i<=$end;$i++){if($array[$i]<$array[$mid]){$mid++;$tmp=$array[$i];$array[$i]=$array[$mid];$array[$mid]=$tmp;}}$tmp=$array[$start];$array[$start]=$array[$mid];$array[$mid]=$tmp;quick_sort($array,$start,$mid-1);quick_sort($array,$mid+1,$end);}方法三:该方法基本上是教科书式的常见写法,首先从左向右遍历小于中间元素的跳过,同时从右向左遍历遇到大的元素跳过,然后如果没有交叉着交换两边值,继续循环,直到找到中间点。注意该方法在处理相同元素的时候,仍旧交换,这样在最坏情况下也有O(nlogn)效率。但下面的函数中,如果将$array[$right]>$key改成$array[$right]>=$key或将$array[$left]<$key改成$array[$left]<=$key则最坏情况不但会堕落为O(n*n).而且除了每次比较的消耗外,还会产生n次交互的额外开销。该题还有另外两个考点,针对死记硬背的同学:1:中间的两个while可否互换。当然不能互换,因为对于快盘需要一个额外的空间保存初始的左值,这样左右互换的时候,先用右边覆盖已经保存为中值的左值,否则会出现问题。见这句$array[$left]=$array[$right];2:$array[$right]=$key;该语句含义可否省略。该句不能省略,大家可以考虑一个极端情况比如两个值的排序(5,2),逐步看下就明白了。代码如下:functionquick_sort_swap(&$array,$start,$end){if($end<=$start)return;$key=$array[$start];$left=$start;$right=$end;while($left<$right){while($left<$right&&$array[$right]>$key)$right--;$array[$left]=$array[$right];while($left<$right&&$array[$left]<$key)$left++;$array[$right]=$array[$left];}$array[$right]=$key;quick_sort_swap(&$array,$start,$right-1);quick_sort_swap(&$array,$right+1,$end);}