コミュニティ
学ぶ
ツールライブラリ
AIツール
レジャー
検索
日本語
目次
迭代法 quickSortIter.php
执行时间测试脚本 test.php
5000次执行时间效率对比
实现代码
递归法 quickSortRec.php
5000実行時間効率比較
ホームページ バックエンド開発 PHPチュートリアル PHP クイックソート問題の再帰的アルゴリズムの実装と反復アルゴリズムの実装

PHP クイックソート問題の再帰的アルゴリズムの実装と反復アルゴリズムの実装

不言
不言
Apr 17, 2018 pm 01:56 PM
php アルゴリズム 再帰

この記事では、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;
}
ログイン後にコピー
ログイン後にコピー
quickSortRec.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

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

}
ログイン後にコピー
ログイン後にコピー

执行时间测试脚本 test.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;
}
ログイン後にコピー
ログイン後にコピー

5000次执行时间效率对比

模式/执行ms时间平均数（数组长度1000）方差（数组长度1000）
迭代 Iter /ms2.8405724760.03862993
递归 Rec /ms3.0713635680.06567554
模式平均数（数组长度400）方差（数组长度400）
迭代 Iter /ms0.9876660350.015847294
递归 Rec /ms0.9879476070.036398175
模式平均数（数组长度50）方差（数组长度50）
迭代 Iter /ms0.0814548970.000522679
递归 Rec /ms0.0665463920.000362922

实现代码

代码地址：https://github.com/ParrySMS/Exp/tree/master/ProLang/quickSort

递归法 quickSortRec.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.php実行時間テストスクリプトtest.php

rrreee

5000実行時間効率比較

モード/実行ms時間 平均(配列長1000) 分散(配列)長さ 1000)
反復 Iter /ms 2.840572476 0.03862993
Recursive Rec /ms 3.071363 568 0.06567554
モード 平均数値(配列長さ 400) 分散 (配列長 400)
Iteration Iter /ms 0.987666035 0.015847294
Recursive Rec /ms 0.987947607 0.036398175

... Recursive Rec/ms実装コードコードアドレス: https://github.com/ParrySMS/Exp/tree/master/ProLang/quickSort再帰メソッドquickSortRec .php反復メソッド quickSortIter.php実行時間テストスクリプト test.phprrreee5000実行時間効率比較分散(配列長1000)
0.066546392 0.000362922
rrreeerrreee
モード/実行ms時間

平均(配列長1000)

反復/ms

2.840572476 0.03862993

再帰 c /ms

🎜3.071363568🎜🎜0.06567554🎜🎜🎜 + 4🎜🎜🎜🎜再帰的記録/ms🎜🎜0.987947607 + 🎜0.081454897🎜🎜0.0005 22679🎜🎜🎜🎜 再帰的 Rec /ms🎜🎜0.066546392🎜🎜0.000362922🎜🎜🎜🎜🎜🎜関連推奨事項: 🎜🎜🎜PHPソートバブルソート🎜🎜🎜🎜PHPソートアルゴリズムシリーズ挿入ソート例共有🎜 🎜🎜🎜PHPソートアルゴリズムパイルソートの詳しい説明🎜🎜

以上がPHP クイックソート問題の再帰的アルゴリズムの実装と反復アルゴリズムの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

Video Face Swap

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

もっと見る

人気の記事

アサシンのクリードシャドウズ：シーシェルリドルソリューション
3週間前 By DDD
Windows11 KB5054979の新しいものと更新の問題を修正する方法
2週間前 By DDD
Atomfallのクレーンコントロールキーカードを見つける場所
3週間前 By DDD
<🎜>：Dead Rails-すべての課題を完了する方法
4週間前 By DDD
Atomfall Guide：アイテムの場所、クエストガイド、およびヒント
1 か月前 By DDD
もっと見る

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト（SublimeText3）

もっと見る

ホットトピック

Gmailメールのログイン入り口はどこですか？
7681
15
Java チュートリアル
1639
14
CakePHP チュートリアル
1393
52
Laravel チュートリアル
1286
25
PHP チュートリアル
1229
29
もっと見る
Related knowledge
Ubuntu および Debian 用の PHP 8.4 インストールおよびアップグレード ガイド Ubuntu および Debian 用の PHP 8.4 インストールおよびアップグレード ガイド Dec 24, 2024 pm 04:42 PM

PHP 8.4 では、いくつかの新機能、セキュリティの改善、パフォーマンスの改善が行われ、かなりの量の機能の非推奨と削除が行われています。 このガイドでは、Ubuntu、Debian、またはその派生版に PHP 8.4 をインストールする方法、または PHP 8.4 にアップグレードする方法について説明します。

今まで知らなかったことを後悔している 7 つの PHP 関数 今まで知らなかったことを後悔している 7 つの PHP 関数 Nov 13, 2024 am 09:42 AM

あなたが経験豊富な PHP 開発者であれば、すでにそこにいて、すでにそれを行っていると感じているかもしれません。あなたは、運用を達成するために、かなりの数のアプリケーションを開発し、数百万行のコードをデバッグし、大量のスクリプトを微調整してきました。

PHP 開発用に Visual Studio Code (VS Code) をセットアップする方法 PHP 開発用に Visual Studio Code (VS Code) をセットアップする方法 Dec 20, 2024 am 11:31 AM

Visual Studio Code (VS Code とも呼ばれる) は、すべての主要なオペレーティング システムで利用できる無料のソース コード エディター (統合開発環境 (IDE)) です。 多くのプログラミング言語の拡張機能の大規模なコレクションを備えた VS Code は、

JSON Web Tokens（JWT）とPHP APIでのユースケースを説明してください。 JSON Web Tokens（JWT）とPHP APIでのユースケースを説明してください。 Apr 05, 2025 am 12:04 AM

JWTは、JSONに基づくオープン標準であり、主にアイデンティティ認証と情報交換のために、当事者間で情報を安全に送信するために使用されます。 1。JWTは、ヘッダー、ペイロード、署名の3つの部分で構成されています。 2。JWTの実用的な原則には、JWTの生成、JWTの検証、ペイロードの解析という3つのステップが含まれます。 3. PHPでの認証にJWTを使用する場合、JWTを生成および検証でき、ユーザーの役割と許可情報を高度な使用に含めることができます。 4.一般的なエラーには、署名検証障害、トークンの有効期限、およびペイロードが大きくなります。デバッグスキルには、デバッグツールの使用とロギングが含まれます。 5.パフォーマンスの最適化とベストプラクティスには、適切な署名アルゴリズムの使用、有効期間を合理的に設定することが含まれます。

PHPでHTML/XMLを解析および処理するにはどうすればよいですか？ PHPでHTML/XMLを解析および処理するにはどうすればよいですか？ Feb 07, 2025 am 11:57 AM

このチュートリアルでは、PHPを使用してXMLドキュメントを効率的に処理する方法を示しています。 XML（拡張可能なマークアップ言語）は、人間の読みやすさとマシン解析の両方に合わせて設計された多用途のテキストベースのマークアップ言語です。一般的にデータストレージに使用されます

母音を文字列にカウントするPHPプログラム 母音を文字列にカウントするPHPプログラム Feb 07, 2025 pm 12:12 PM

文字列は、文字、数字、シンボルを含む一連の文字です。このチュートリアルでは、さまざまな方法を使用してPHPの特定の文字列内の母音の数を計算する方法を学びます。英語の母音は、a、e、i、o、u、そしてそれらは大文字または小文字である可能性があります。 母音とは何ですか？ 母音は、特定の発音を表すアルファベットのある文字です。大文字と小文字など、英語には5つの母音があります。 a、e、i、o、u 例1 入力：string = "tutorialspoint" 出力：6 説明する 文字列「TutorialSpoint」の母音は、u、o、i、a、o、iです。合計で6元があります

PHPでの後期静的結合を説明します（静的：:)。 PHPでの後期静的結合を説明します（静的：:)。 Apr 03, 2025 am 12:04 AM

静的結合（静的：:) PHPで後期静的結合（LSB）を実装し、クラスを定義するのではなく、静的コンテキストで呼び出しクラスを参照できるようにします。 1）解析プロセスは実行時に実行されます。2）継承関係のコールクラスを検索します。3）パフォーマンスオーバーヘッドをもたらす可能性があります。

PHPマジックメソッド（__construct、__destruct、__call、__get、__setなど）とは何ですか？ PHPマジックメソッド（__construct、__destruct、__call、__get、__setなど）とは何ですか？ Apr 03, 2025 am 12:03 AM

PHPの魔法の方法は何ですか？ PHPの魔法の方法には次のものが含まれます。1。\ _ \ _コンストラクト、オブジェクトの初期化に使用されます。 2。\ _ \ _リソースのクリーンアップに使用される破壊。 3。\ _ \ _呼び出し、存在しないメソッド呼び出しを処理します。 4。\ _ \ _ get、dynamic属性アクセスを実装します。 5。\ _ \ _セット、動的属性設定を実装します。これらの方法は、特定の状況で自動的に呼び出され、コードの柔軟性と効率を向上させます。

See all articles