집 > 기사 > 백엔드 개발 > PHP 빠른 정렬 문제에 대한 재귀 알고리즘 구현 및 반복 알고리즘 구현

PHP 빠른 정렬 문제에 대한 재귀 알고리즘 구현 및 반복 알고리즘 구현

不言원래의: 2018-04-17 13:56:441909검색

이 글은 PHP 빠른 정렬 문제에서 재귀 알고리즘과 반복 알고리즘의 구현을 소개합니다. 이제 이를 여러분과 공유합니다. 도움이 필요한 친구들은 이를 참조할 수 있습니다

구현 코드

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

재귀적 방법 `quickSortRec.phpquickSortRec.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(&#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次执行时间效率对比

模式/执行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(&#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>

반복적 방법 quickSortIter.php

rrreee

실행 시간 테스트 스크립트 test.phprrreee5000 실행 시간 효율성 비교Mode/Execution ms timeAverage(배열 길이 1000) Variance(배열 길이 1000)반복 반복 /ms2.8405724760.03862993재귀 기록 /ms3.071363 5680.06567554

Mode평균 숫자(배열 길이 400) 분산(배열 길이 400) Iteration Iter /ms0.9876660350.015847294Recursive Rec /ms0.9879476070.036398175

Recursive Rec/ms0.0665463920.000362922 rrreee반복 방법 quickSortIter.phprrreee

rrreee모드/실행 ms 시간 평균(배열 길이 1000)

...
구현 코드	코드 주소: https://github.com/ParrySMS/Exp/tree/master/ProLang/quickSort	재귀 메서드 `quickSortRec .php`
실행 시간 테스트 스크립트 `test.php`	5000 실행 시간 효율성 비교

분산(배열 길이 1000)

/ms

2.840572476

0.03862993

🎜🎜재귀적 c /ms🎜 🎜3.071363568🎜🎜0.06567554🎜🎜🎜 + 4🎜🎜🎜🎜재귀 기록 /ms🎜🎜0.987947607 + 🎜0.081454897🎜🎜0.000522 679🎜🎜🎜🎜 재귀 기록 /ms🎜🎜0.066546392🎜🎜0.000362922🎜🎜🎜🎜🎜🎜관련 권장 사항: 🎜🎜🎜PHP 정렬 버블 정렬🎜🎜🎜🎜PHP 정렬 알고리즘 시리즈 삽입 정렬 예제 공유🎜 🎜🎜🎜PHP 정렬 알고리즘의 힙 정렬에 대한 자세한 설명🎜🎜

위 내용은 PHP 빠른 정렬 문제에 대한 재귀 알고리즘 구현 및 반복 알고리즘 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명：

이전 기사：ODBC를 사용하여 PHP에서 SQL Server 데이터베이스에 연결다음 기사：ODBC를 사용하여 PHP에서 SQL Server 데이터베이스에 연결

PHP 빠른 정렬 문제에 대한 재귀 알고리즘 구현 및 반복 알고리즘 구현

구현 코드

재귀적 방법 quickSortRec.phpquickSortRec.php

迭代法 quickSortIter.php

执行时间测试脚本 test.php

5000次执行时间效率对比

实现代码

递归法 quickSortRec.php

迭代法 quickSortIter.php

rrreee

관련 기사

재귀적 방법 `quickSortRec.phpquickSortRec.php`

迭代法 `quickSortIter.php`

执行时间测试脚本 `test.php`

递归法 `quickSortRec.php`

迭代法 `quickSortIter.php`