PHP遞歸效率分析

而且是差了3倍的效率。所以，PHP中的遞歸一定要小心的對待。就跟隨本站小編一起去了解下吧，想了解更多相關信息請持續關注我們應屆畢業生考試網!

最近寫了一個快速排序的算法，發現PHP中的遞歸效率不能一刀切，在各種不同的服務器中，可能會表現不一樣。

　　複製代碼 代碼如下:

function qsort(&$arr)

{

_quick_sort($arr, 0, count($arr) - 1);

}

/**

* 採用遞歸算法的快速排序。

*

* @param array $arr 要排序的數組

* @param int $low 最低的排序子段

* @param int $high 最高的排序字段

*/

function _quick_sort(&$arr, $low, $high)

{

$low_data = $arr[$low];

$prev_low = $low;

$prev_high = $high;

while ($low < $high)

{

while ($arr[$high] >= $low_data && $low < $high) {

$high--;

}

if ($low < $high) {

$arr[$low] = $arr[$high];

$low++;

}

while ($arr[$low] <= $low_data && $low < $high) {

$low++;

}

if ($low < $high) {

$arr[$high] = $arr[$low];

$high--;

}

}

$arr[$low] = $low_data;

if ($prev_low < $low) {

_quick_sort($arr, $prev_low, $low);

}

if ($low + 1 < $prev_high) {

_quick_sort($arr, $low + 1, $prev_high);

}

}

function quick_sort(&$arr)

{

$stack = array();

array_push($stack, 0);

array_push($stack, count($arr) -1);

while (!empty($stack)) {

$high = array_pop($stack);

$low = array_pop($stack);

$low_data = $arr[$low];

$prev_low = $low;

$prev_high = $high;

while ($low < $high)

{

while ($arr[$high] >= $low_data && $low < $high) {

$high--;

}

if ($low < $high) {

$arr[$low] = $arr[$high];

$low++;

}

while ($arr[$low] <= $low_data && $low < $high) {

$low++;

}

if ($low < $high) {

$arr[$high] = $arr[$low];

$high--;

}

}

$arr[$low] = $low_data;

if ($prev_low < $low) {

array_push($stack, $prev_low);

array_push($stack, $low);

}

if ($low + 1 < $prev_high) {

array_push($stack, $low + 1);

array_push($stack, $prev_high);

}

}

}

下面是測試速度的`代碼：

複製代碼 代碼如下:

function qsort_test1()

{

$arr = range(1, 1000);

shuffle($arr);

$arr2 = $arr;

$t1 = microtime(true);

quick_sort($arr2);

$t2 = microtime(true) - $t1;

echo "非遞歸調用的花費：" . $t2 . "n";

$arr1 = $arr;

$t1 = microtime(true);

qsort($arr1);

$t2 = microtime(true) - $t1;

echo "遞歸調用的花費：" . $t2 . "n";

｝

在我的IIS 服務器上（CGI）模式，我的測試結果是：

非遞歸調用的花費：0.036401009559631

遞歸調用的花費：0.053439617156982

在我的Apache 服務器上，我的測試結果是：

非遞歸調用的花費：0.022789001464844

遞歸調用的花費：0.014809131622314

結果完全相反，而PHP的版本是一樣的。

看來對遞歸的效率要具體問題具體分析了。</p