この記事では、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('SORT_TIMES', 100);
define('SIZE', 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 /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-17
* Time: 23:45
*/require "quickSortIter.php";require "quickSortRec.php";
define('SORT_TIMES', 100);
define('SIZE', 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
0.066546392 |
0.000362922 |
|
実装コード
コードアドレス: https://github.com/ParrySMS/Exp/tree/master/ProLang/quickSort | 再帰メソッドquickSortRec .php
rrreee | 反復メソッド quickSortIter.php
rrreee
| 実行時間テストスクリプト test.php
rrreee5000実行時間効率比較 |
|
モード/実行ms時間
平均(配列長1000) |
分散(配列長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 サイトの他の関連記事を参照してください。