關於合併排序在php下的問題

Question

我一直試圖在php下實現合併排序。但似乎不成功:(無法找到錯誤的根源任何形式的幫助是非常讚賞

function merge_sort(&$input, $start, $end) { 
    if($start < $end) { 
     $mid = (int) floor($start + $end/2); 
     merge_sort($input, $start, $mid); 
     merge_sort($input, $mid + 1, $end); 
     merge($input, $start, $mid, $end); 
    } 
} 

function merge(&$input, $p, $q, $r) { 
    $a = $q - $p + 1; 
    $b = $r - $q; 

    for($i = $p;$i <= $q;$i++) { 
     $arr1[] = $input[$i]; 
    } 

    for($i = $q+1;$i <= $r;$i++) { 
     $arr2[] = $input[$i]; 
    } 

    $c = $d = 0; 
    for($i = $p; $i <= $r; $i++) { 
     $s = $arr1[$c]; 
     $t = $arr2[$d]; 

     if($a && (($s <= $t) || !$b)) { 
      $input[$i] = $s; 
      $a--;$c++; 
     } else if($b) { 
      $input[$i] = $t; 
      $b--;$d++; 
     } 
    } 
    return true; 
} 

這裏的信息Xdebug的扔回去。！

Fatal error: Maximum function nesting level of '100' reached, aborting! 

Answer 1

有一個最大的功能嵌套級別'100'，並且已經達到了它。你的遞歸函數進入太深。

Answer 2

設置

xdebug.max_nesting_level=500 

在我的php.ini

Answer 3

從http://www.xdebug.org/docs/all_settings：

xdebug.max_nesting_level 類型：整數，默認值：100個 控制保護機制，無限遞歸保護。此設置的值是腳本中止前允許的嵌套函數的最大級別。

你在遞歸函數中觸發了這個xdebug錯誤太深了。嘗試提高這個限制，看看是否有幫助。

而且，這裏大約是遞歸和PHP一篇有趣的文章：http://www.alternateinterior.com/2006/09/tail-recursion-in-php.html

Answer 4

PHP不是遞歸算法良好的語言。來自manual：

有可能在PHP中調用遞歸函數 。但是，請避免使用 遞歸函數/方法調用 超過100-200遞歸級別，因爲它可以粉碎堆棧並導致當前腳本終止 。

如果您需要在PHP中執行此操作，您可能需要找到算法的迭代版本。您已經達到了語言中硬編碼的限制。

Answer 5

要在合併排序上達到100的嵌套級別，您需要有一個大小爲2^100（大約1e30）的輸入數組，這是不可能的。我懷疑你的遞歸是不正確的。例如，您寫了$start + $end/2而不是($start + $end)/2。

Answer 6

Cosi dovrebbe funzionare !!!! www.dslpg.it

function merge (&$a, $left, $center, $right) { //left = p right = r center = q 
    $n1 = $center - $left + 1; 
    $n2 = $right - $center; 
    for ($i = 1; $i <= $n1; $i++) $L[$i] = $a[$left+$i-1]; 
    for ($i = 1; $i <= $n2; $i++) $R[$i] = $a[$center+$i]; 
    $L[$n1+1] = 99999; 
    $R[$n2+1] = 99999; 
    $i = 1; 
    $j = 1; 
    for ($k = $left; $k <= $right; $k++) { 
     if ($L[$i] <= $R[$j]) { 
      $a[$k] = $L[$i]; 
      echo $a[$k]; 
      $i++; 
     } 
     else { 
      $a[$k] = $R[$j]; 
      echo $a[$k]; 
      $j++; 
     } 
    } 
    return $a; 
} 
function merge_sort (&$a, $left, $right) { //left = p right = r 
    if ($left < $right) { 
     $center = (int) floor(($left + $right)/2); 

     merge_sort ($a, $left, $center); 
     merge_sort ($a, $center+1, $right); 
     merge ($a, $left, $center, $right); 
    } 
} 
merge_sort ($a, 1, $n); 

Answer 7

這是我工作的解決方案，隨時進行比較......

/** 
* @param array $items array to sort 
* @param int $l  left index (defaults to 0) 
* @param int $r  right index (defaults to count($items)-1) 
*/ 
function mergeSort(&$items, $l = 0, $r = null) 
{ 
    if (!isset($r)) { 
     $r = count($items) - 1; 
    } 

    if ($l < $r) { 
     $m = floor(($r - $l)/2) + $l; 
     mergeSort($items, $l, $m); 
     mergeSort($items, $m + 1, $r); 
     merge($items, $l, $m, $r); 
    } 
} 

/** 
* @param array $items array to merge 
* @param int $l  left index 
* @param int $m  middle index 
* @param int $r  right index 
*/ 
function merge(&$items, $l, $m, $r) 
{ 
    $itemsA = array_slice($items, $l, $m + 1 - $l); 
    $itemsB = array_slice($items, $m + 1, ($r + 1) - ($m + 1)); 

    $a = 0; 
    $aCount = count($itemsA); 
    $b = 0; 
    $bCount = count($itemsB); 

    for ($i = $l; $i <= $r; $i++) { 
     if ($a < $aCount && ($b == $bCount || $itemsA[$a] <= $itemsB[$b])) { 
      $items[$i] = $itemsA[$a++]; 
     } else { 
      $items[$i] = $itemsB[$b++]; 
     } 
    } 
} 

$items = array(5,3,6,1,2,3,9,10,7,2,4,8); 
mergeSort($items); 
echo implode(',', $items) . "\n"; 

輸出：

1,2,2,3,3,4,5,6,7,8,9,10