PHP
发布时间:2019-11-14 发布网站:大佬教程 code.js-code.com
大佬教程收集整理的这篇文章主要介绍了php实现快速排序的三种方法分享,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
写了三种php快速排示例,第一种效率低但最简单最容易理解,第二个是算法导论上提供的单向一次遍历找中值方法,第三种是双向遍历找中值经典快排算法。三组算法实现和比较如下:方法一:该方法比较直观,但损失了大量的空间为代价,使用了效率较低的merge函数。在三种方法中效率最低。最坏情况下算法退化为(O(n*n))
function quick_sort($array)
{if(count($array) <= 1) return $array;
$key = $array
[0];
$rightArray = array(
);$leftArray = array(
);for($i = 1; $i < count($array
); $i++)
{ if($arra
Y[$i] >= $key)
{$rightArra
Y[] = $arra
Y[$i];
} else
{$leftArra
Y[] = $arra
Y[$i];
}
}
$leftArray = quick_sort($leftArray
);$rightArray = quick_sort($rightArray
);return array_merge($leftArray,array($key),$rightArray
);}
方法二:该算法来自算法导论,叫作Nico Lomuto方法(感兴趣goole上有详细说明)使用最经典的单方向一次遍历找到中值。
但这种算法在最坏情况下(例如值相同的数组,需要n-1次划分,每一次划分需要O(n) 时间去掉一个元素)最坏情况下为O(n*n)
function quick_sort(&$array,$start,$end)
{ if ($start >= $end) return;
$mid = $start;
for ($i = $start + 1; $i <= $end; $i++)
{if ($arra
Y[$i] < $arra
Y[$mid])
{ $mid++;
$tmp = $arra
Y[$i];
$arra
Y[$i] = $arra
Y[$mid];
$arra
Y[$mid] = $tmp;
}
}
$tmp = $arra
Y[$start];
$arra
Y[$start] = $arra
Y[$mid];
$arra
Y[$mid] = $tmp;
quick_sort($array,$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),逐步看下就明白了。
function quick_sort_swap(&$array,$end)
{if($end <= $start) return;
$key = $arra
Y[$start];
$left = $start;
$right = $end;
while($left < $right)
{while($left < $right && $array[$right] > $key)
$right--;
$arra
Y[$left] = $arra
Y[$right];
while($left < $right && $arra
Y[$left] < $key)
$left++;
$arra
Y[$right] = $arra
Y[$left];
}
$arra
Y[$right] = $key;
quick_sort_swap(&$array,$right - 1
);quick_sort_swap(&$array,$right+1,$end
);}
大佬总结
以上是大佬教程为你收集整理的php实现快速排序的三种方法分享全部内容,希望文章能够帮你解决php实现快速排序的三种方法分享所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。