Recursive algorithm implementation and iterative algorithm implementation for PHP quick sorting problem

The content of this article is about the implementation of recursive algorithm and iterative algorithm for quick sorting problem in PHP. It has certain reference value. Now I share it with you. Friends in need can refer to it

implementation Code

Code address: https://github.com/ParrySMS/Exp/tree/master/ProLang/quickSort

Recursive methodquickSortRec .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);

}

Iteration methodquickSortIter.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;
}

---

Execution time test scripttest.php

<?php/**
 * Created by PhpStorm.
 * User: L
 * Date: 2018-4-17
 * Time: 23:45
 */require "quickSortIter.php";require "quickSortRec.php";

define(&#39;SORT_TIMES&#39;, 100);
define(&#39;SIZE&#39;, 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 execution time efficiency comparison

Mode/Execution ms time	Average (array length 1000)	Variance ( Array length 1000)
Iterate Iter /ms	2.840572476	0.03862993
RecursiveRec /ms	3.071363568	0.06567554

#ModeAverage (array length 400) Variance (array length 400) IterateIter /ms0.9876660350.015847294Recursive Rec /ms0.9879476070.036398175 ModeMean (array length 50)Variance (array length 50)IterativeIter /ms0.0814548970.000522679RecursiveRec /ms0.0665463920.000362922Implementation code

Code address: https://github.com/ParrySMS/Exp/tree/master/ProLang/quickSort

Recursive method

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);

}

Iterative method

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;
}

---

Execution time test script

test .php

<?php/**
 * Created by PhpStorm.
 * User: L
 * Date: 2018-4-17
 * Time: 23:45
 */require "quickSortIter.php";require "quickSortRec.php";

define(&#39;SORT_TIMES&#39;, 100);
define(&#39;SIZE&#39;, 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 execution time efficiency comparison

Mode/Execution ms timeAverage (array length 1000 )Variance (array length 1000)IterateIter /ms2.8405724760.03862993Recursive Rec /ms3.0713635680.06567554 ModeAverage (array length 400) Variance (array length 400) ##Iterate Iter / msRecursive Rec /ms

0.987666035	0.015847294
0.987947607	0.036398175

ModeIterativeIter /msRecursiveRec /ms ##Related recommendations:

Average (array length 50)	Variance (array length 50)
0.081454897	0.000522679
0.066546392	0.000362922

Bubble sorting of PHP sorting

PHP sorting algorithm series insertion sort example sharing

PHP sorting algorithm heap sorting detailed explanation

The above is the detailed content of Recursive algorithm implementation and iterative algorithm implementation for PHP quick sorting problem. For more information, please follow other related articles on the PHP Chinese website!