搜索
首页后端开发php教程php实现快速排序的三种方法_PHP教程

php实现快速排序的三种方法_PHP教程

Jul 13, 2016 am 10:36 AM
php主要实现快速排序文章方法

这篇文章主要介绍了php实现快速排序的三种方法,三种方法各有优缺点,需要的朋友可以参考下

写了三种php快速排示例,第一种效率低但最简单最容易理解,第二个是算法导论上提供的单向一次遍历找中值方法,第三种是双向遍历找中值经典快排算法。三组算法实现和比较如下:

 

方法一:该方法比较直观,但损失了大量的空间为代价,使用了效率较低的merge函数。在三种方法中效率最低。最坏情况下算法退化为(O(n*n))

 代码如下:

function quick_sort($array) {

 if(count($array)

 $key = $array[0];

 $rightArray = array();

 $leftArray = array();

 for($i = 1; $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

 if ($array[$i]

     $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]

 

情况不但会堕落为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

 $key = $array[$start];

 $left = $start;

 $right = $end;

 while($left

  while($left $key)

   $right--;

  $array[$left] = $array[$right];

  while($left

   $left++;

  $array[$right] = $array[$left];

 }

 $array[$right] = $key;

 quick_sort_swap(&$array, $start, $right - 1);

 quick_sort_swap(&$array, $right+1, $end);

}

 

www.bkjia.comtruehttp://www.bkjia.com/PHPjc/740818.htmlTechArticle这篇文章主要介绍了php实现快速排序的三种方法,三种方法各有优缺点,需要的朋友可以参考下 写了三种php快速排示例,第一种效率低但最...
声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
哪些常见问题会导致PHP会话失败?哪些常见问题会导致PHP会话失败?Apr 25, 2025 am 12:16 AM

PHPSession失效的原因包括配置错误、Cookie问题和Session过期。1.配置错误:检查并设置正确的session.save_path。2.Cookie问题:确保Cookie设置正确。3.Session过期:调整session.gc_maxlifetime值以延长会话时间。

您如何在PHP中调试与会话相关的问题?您如何在PHP中调试与会话相关的问题?Apr 25, 2025 am 12:12 AM

在PHP中调试会话问题的方法包括:1.检查会话是否正确启动;2.验证会话ID的传递;3.检查会话数据的存储和读取;4.查看服务器配置。通过输出会话ID和数据、查看会话文件内容等方法,可以有效诊断和解决会话相关的问题。

如果session_start()被多次调用会发生什么?如果session_start()被多次调用会发生什么?Apr 25, 2025 am 12:06 AM

多次调用session_start()会导致警告信息和可能的数据覆盖。1)PHP会发出警告,提示session已启动。2)可能导致session数据意外覆盖。3)使用session_status()检查session状态,避免重复调用。

您如何在PHP中配置会话寿命?您如何在PHP中配置会话寿命?Apr 25, 2025 am 12:05 AM

在PHP中配置会话生命周期可以通过设置session.gc_maxlifetime和session.cookie_lifetime来实现。1)session.gc_maxlifetime控制服务器端会话数据的存活时间,2)session.cookie_lifetime控制客户端cookie的生命周期,设置为0时cookie在浏览器关闭时过期。

使用数据库存储会话的优点是什么?使用数据库存储会话的优点是什么?Apr 24, 2025 am 12:16 AM

使用数据库存储会话的主要优势包括持久性、可扩展性和安全性。1.持久性:即使服务器重启,会话数据也能保持不变。2.可扩展性:适用于分布式系统,确保会话数据在多服务器间同步。3.安全性:数据库提供加密存储,保护敏感信息。

您如何在PHP中实现自定义会话处理?您如何在PHP中实现自定义会话处理?Apr 24, 2025 am 12:16 AM

在PHP中实现自定义会话处理可以通过实现SessionHandlerInterface接口来完成。具体步骤包括:1)创建实现SessionHandlerInterface的类,如CustomSessionHandler;2)重写接口中的方法(如open,close,read,write,destroy,gc)来定义会话数据的生命周期和存储方式;3)在PHP脚本中注册自定义会话处理器并启动会话。这样可以将数据存储在MySQL、Redis等介质中,提升性能、安全性和可扩展性。

什么是会话ID?什么是会话ID?Apr 24, 2025 am 12:13 AM

SessionID是网络应用程序中用来跟踪用户会话状态的机制。1.它是一个随机生成的字符串,用于在用户与服务器之间的多次交互中保持用户的身份信息。2.服务器生成并通过cookie或URL参数发送给客户端,帮助在用户的多次请求中识别和关联这些请求。3.生成通常使用随机算法保证唯一性和不可预测性。4.在实际开发中,可以使用内存数据库如Redis来存储session数据,提升性能和安全性。

您如何在无状态环境(例如API)中处理会议?您如何在无状态环境(例如API)中处理会议?Apr 24, 2025 am 12:12 AM

在无状态环境如API中管理会话可以通过使用JWT或cookies来实现。1.JWT适合无状态和可扩展性,但大数据时体积大。2.Cookies更传统且易实现,但需谨慎配置以确保安全性。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

适用于 Eclipse 的 SAP NetWeaver 服务器适配器

适用于 Eclipse 的 SAP NetWeaver 服务器适配器

将Eclipse与SAP NetWeaver应用服务器集成。

WebStorm Mac版

WebStorm Mac版

好用的JavaScript开发工具

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版

MinGW - 适用于 Windows 的极简 GNU

MinGW - 适用于 Windows 的极简 GNU

这个项目正在迁移到osdn.net/projects/mingw的过程中,你可以继续在那里关注我们。MinGW:GNU编译器集合(GCC)的本地Windows移植版本,可自由分发的导入库和用于构建本地Windows应用程序的头文件;包括对MSVC运行时的扩展,以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。