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

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

}

Copy after login

Copy after login

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

Copy after login

Copy after login

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>

Copy after login

Copy after login

5000 execution time efficiency comparison

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!