php实现快速排序的三种方法
三种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($array[$i] >= $key) {
$rightArray[] = $array[$i];
} else {
$leftArray[] = $array[$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 ($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),逐步看下就明白了。
代码如下:
function quick_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);
}
-
PHP的漏洞-如何防止PHP漏洞
漏洞无非这么几类,XSS、sql注入、命令执行、上传漏洞、本地包含、远程包含、权限绕过、信息泄露、cookie伪造、CSRF(跨站请求)等。下面是小编为大家带来的关于PHP的漏洞的知识,欢迎阅读。+sql注入其中占大头的自然是XSS与SQL注入,对于框架类型或者有公共文件的,建...
-
PHP文件上传源码分析
文件上传,一般分为俩种方式FTP和HTTP,对于我们的互联网应用来说:FTP上传虽然传输稳定,但是易用性和安全性都是个问题.你总不至于在用户要上传头像的时候告诉用户”请打开FTP客户端,上传文件到中,并以2dk433423l.jpg命名”吧?PHP文件上传源码分析基于HTTP的上传...
-
php多个文件及图片上传实例详解
主要介绍了php多个文件及图片上传的方法,以实例形式详细叙述了多文件上传的原理与实现技巧,非常实用,需要的朋友可以参考下。本文实例讲述了php多个文件及图片上传的方法。分享给大家供大家参考。具体实现方法如下:多个文件上传是在单文件上传的基础上利用遍历...
-
提高PHP执行效率的50个技巧
PHP是一种HTML内嵌式的语言,是一种在服务器端执行的嵌入HTML文档的脚本语言,下面是小编为大家整理的提高PHP执行效率的50个技巧,欢迎参考~1、用单引号代替双引号来包含字符串,这样做会更快一些。因为PHP会在双引号包围的字符串中搜寻变量,单引号则不会,注意:只有echo...