PHP快速排序问题的递归算法实现和迭代算法实现
程序员文章站
2022-03-25 22:36:46
...
这篇文章介绍的内容是关于在PHP快速排序问题的递归算法实现和迭代算法实现 ,有着一定的参考价值,现在分享给大家,有需要的朋友可以参考一下
实现代码
代码地址:https://github.com/ParrySMS/Exp/tree/master/ProLang/quickSort
递归法 quickSortRec.php
<?php/** * Created by PhpStorm. * User: L * Date: 2018-4-13 * Time: 23:27 *//** 递归法快排序 * @param array $ar * @return array */function quickSortR(array $ar){ //判断数组长度 $size = sizeof($ar); if($size<=1){ return $ar; } //用两个数组分别接受比游标key小和比key大的数据 $left = array(); $right = array(); $key = $ar[0]; for($i =1;$i<$size;$i++){ if($ar[$i]<=$key){ $left[] = $ar[$i]; }else{ $right[] = $ar[$i]; } } //内部再进行排序 $left = quickSortR($left); $right = quickSortR($right); //最后合并 return array_merge($left,array($key),$right); }
迭代法 quickSortIter.php
<?php/** * Created by PhpStorm. * User: L * Date: 2018-4-14 * Time: 14:51 *//** 迭代法 * @param array $ar * @return array */function quickSortI(array $ar){ $stack = array($ar); $sort = array(); //判断数组长度 $size = sizeof($ar); if ($size <= 1) { return $ar; } //栈空即跳出循环 while ($stack) { $arr = array_pop($stack); if (count($arr) <= 1) { if (count($arr) == 1) { $sort[] = &$arr[0]; } continue; } $key = $arr[0]; $high = array(); $low = array(); //用两个数组分别接受比游标key小和比key大的数据 $_size = count($arr); for ($i = 1; $i < $_size; $i++) { if ($arr[$i] <= $key) { $high[] = &$arr[$i]; } else { $low[] = &$arr[$i]; } } if (!empty($low)) {//数据入站 array_push($stack, $low); } array_push($stack, array($arr[0])); if (!empty($high)) { array_push($stack, $high); } } return $sort; }
执行时间测试脚本 test.php
<?php/** * Created by PhpStorm. * User: L * Date: 2018-4-17 * Time: 23:45 */require "quickSortIter.php";require "quickSortRec.php"; define('SORT_TIMES', 100); define('SIZE', 1000);function rowTable(){ unset($row); $row = array(); for ($i = 0; $i < SORT_TIMES; $i++) { $row = getSortRow($row); } foreach ($row as $r) { print <<< TR <tr> <td>$r->iter</td> <td>$r->rec</td> </tr> TR; } }function getSortRow(array $row){ unset($ar); $ar = array(); for ($i = 0; $i < SIZE; $i++) { $ar[] = rand(0, SIZE*2); } $stime = microtime(true); $recAr = quickSortR($ar); $etime = microtime(true); $recTime = 1000 * ($etime - $stime);// echo"<br/>"; $stime = microtime(true); $iterAr = quickSortI($ar); $etime = microtime(true); $iterTime = 1000 * ($etime - $stime);// print_r($recAr);// echo "<br/>";// print_r($iterAr); $row[] = (object)["iter" => $iterTime, "rec" => $recTime]; return $row; }?><table border="1"> <tr> <th>迭代 Iter/ms</th> <th>递归 Rec/ms</th> </tr> <?php rowTable(); ?></table>
5000次执行时间效率对比
模式/执行ms时间 | 平均数(数组长度1000) | 方差(数组长度1000) |
---|---|---|
迭代 Iter /ms | 2.840572476 | 0.03862993 |
递归 Rec /ms | 3.071363568 | 0.06567554 |
模式 | 平均数(数组长度400) | 方差(数组长度400) |
---|---|---|
迭代 Iter /ms | 0.987666035 | 0.015847294 |
递归 Rec /ms | 0.987947607 | 0.036398175 |
模式 | 平均数(数组长度50) | 方差(数组长度50) |
---|---|---|
迭代 Iter /ms | 0.081454897 | 0.000522679 |
递归 Rec /ms | 0.066546392 | 0.000362922 |
实现代码
代码地址:https://github.com/ParrySMS/Exp/tree/master/ProLang/quickSort
递归法 quickSortRec.php
<?php/** * Created by PhpStorm. * User: L * Date: 2018-4-13 * Time: 23:27 *//** 递归法快排序 * @param array $ar * @return array */function quickSortR(array $ar){ //判断数组长度 $size = sizeof($ar); if($size<=1){ return $ar; } //用两个数组分别接受比游标key小和比key大的数据 $left = array(); $right = array(); $key = $ar[0]; for($i =1;$i<$size;$i++){ if($ar[$i]<=$key){ $left[] = $ar[$i]; }else{ $right[] = $ar[$i]; } } //内部再进行排序 $left = quickSortR($left); $right = quickSortR($right); //最后合并 return array_merge($left,array($key),$right); }
迭代法 quickSortIter.php
<?php/** * Created by PhpStorm. * User: L * Date: 2018-4-14 * Time: 14:51 *//** 迭代法 * @param array $ar * @return array */function quickSortI(array $ar){ $stack = array($ar); $sort = array(); //判断数组长度 $size = sizeof($ar); if ($size <= 1) { return $ar; } //栈空即跳出循环 while ($stack) { $arr = array_pop($stack); if (count($arr) <= 1) { if (count($arr) == 1) { $sort[] = &$arr[0]; } continue; } $key = $arr[0]; $high = array(); $low = array(); //用两个数组分别接受比游标key小和比key大的数据 $_size = count($arr); for ($i = 1; $i < $_size; $i++) { if ($arr[$i] <= $key) { $high[] = &$arr[$i]; } else { $low[] = &$arr[$i]; } } if (!empty($low)) {//数据入站 array_push($stack, $low); } array_push($stack, array($arr[0])); if (!empty($high)) { array_push($stack, $high); } } return $sort; }
执行时间测试脚本 test.php
<?php/** * Created by PhpStorm. * User: L * Date: 2018-4-17 * Time: 23:45 */require "quickSortIter.php";require "quickSortRec.php"; define('SORT_TIMES', 100); define('SIZE', 1000);function rowTable(){ unset($row); $row = array(); for ($i = 0; $i < SORT_TIMES; $i++) { $row = getSortRow($row); } foreach ($row as $r) { print <<< TR <tr> <td>$r->iter</td> <td>$r->rec</td> </tr> TR; } }function getSortRow(array $row){ unset($ar); $ar = array(); for ($i = 0; $i < SIZE; $i++) { $ar[] = rand(0, SIZE*2); } $stime = microtime(true); $recAr = quickSortR($ar); $etime = microtime(true); $recTime = 1000 * ($etime - $stime);// echo"<br/>"; $stime = microtime(true); $iterAr = quickSortI($ar); $etime = microtime(true); $iterTime = 1000 * ($etime - $stime);// print_r($recAr);// echo "<br/>";// print_r($iterAr); $row[] = (object)["iter" => $iterTime, "rec" => $recTime]; return $row; }?><table border="1"> <tr> <th>迭代 Iter/ms</th> <th>递归 Rec/ms</th> </tr> <?php rowTable(); ?></table>
5000次执行时间效率对比
模式/执行ms时间 | 平均数(数组长度1000) | 方差(数组长度1000) |
---|---|---|
迭代 Iter /ms | 2.840572476 | 0.03862993 |
递归 Rec /ms | 3.071363568 | 0.06567554 |
模式 | 平均数(数组长度400) | 方差(数组长度400) |
---|---|---|
迭代 Iter /ms | 0.987666035 | 0.015847294 |
递归 Rec /ms | 0.987947607 | 0.036398175 |
模式 | 平均数(数组长度50) | 方差(数组长度50) |
---|---|---|
迭代 Iter /ms | 0.081454897 | 0.000522679 |
递归 Rec /ms | 0.066546392 | 0.000362922 |
以上就是PHP快速排序问题的递归算法实现和迭代算法实现 的详细内容,更多请关注其它相关文章!
下一篇: PHP输出gzip压缩