Heim > Artikel > Backend-Entwicklung > Rekursive Algorithmusimplementierung und iterative Algorithmusimplementierung für PHP-Schnellsortierungsprobleme

Rekursive Algorithmusimplementierung und iterative Algorithmusimplementierung für PHP-Schnellsortierungsprobleme

不言Original: 2018-04-17 13:56:441906Durchsuche

Dieser Artikel stellt die Implementierung des rekursiven Algorithmus und des iterativen Algorithmus im PHP-Schnellsortierungsproblem vor. Jetzt kann ich ihn mit Ihnen teilen

Implementierungscode

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

Rekursive Methode`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);

}

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

Ausführungszeit-Testskript`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-Ausführungszeit-Effizienzvergleich

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

Implementierungscode

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

Rekursive Methode `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 Methode`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;
}

Testskript zur Ausführungszeit`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 Ausführungszeiteffizienz Vergleichen

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

Modus

Durchschnitt (Array-Länge 50)

Varianz (Array-Länge 50)

Iterate Iter /ms

0.081454897

0.000522679

Rekursive Rec /ms

0.066546392

0.000362922

模式	平均数（数组长度50）	方差（数组长度50）
迭代 Iter /ms	0.081454897	0.000522679
递归 Rec /ms	0.066546392	0.000362922

Verwandte Empfehlungen:

Blasensortierung der PHP-Sortierung

Beispiel für die Einfügungssortierung der PHP-Sortieralgorithmusserien

PHP-Sortierung Detaillierte Erklärung der Algorithmus-Heap-Sortierung

Das obige ist der detaillierte Inhalt vonRekursive Algorithmusimplementierung und iterative Algorithmusimplementierung für PHP-Schnellsortierungsprobleme. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme：

Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Vorheriger Artikel：Verwenden Sie ODBC, um eine Verbindung zur SQL Server-Datenbank in PHP herzustellenNächster Artikel：Verwenden Sie ODBC, um eine Verbindung zur SQL Server-Datenbank in PHP herzustellen

In Verbindung stehende Artikel

Mehr sehen

Rekursive Algorithmusimplementierung und iterative Algorithmusimplementierung für PHP-Schnellsortierungsprobleme

Implementierungscode

Rekursive MethodequickSortRec.php

IterationsmethodequickSortIter.php

Ausführungszeit-Testskripttest.php

5000-Ausführungszeit-Effizienzvergleich

Implementierungscode

Rekursive Methode quickSortRec.php

Iterative MethodequickSortIter.php

Testskript zur Ausführungszeittest.php

5000 Ausführungszeiteffizienz Vergleichen

In Verbindung stehende Artikel

Rekursive Methode`quickSortRec.php`

Iterationsmethode`quickSortIter.php`

Ausführungszeit-Testskript`test.php`

Rekursive Methode `quickSortRec.php`

Iterative Methode`quickSortIter.php`

Testskript zur Ausführungszeit`test.php`