寫作歸併排序

Question

我曾試圖用PHP編寫一個基本的合併排序涉及一小陣，但問題是它需要大約一分鐘左右來執行，並返回：

Fatal error: Allowed memory size of 536870912 bytes exhausted (tried to allocate 35 bytes) in /Users/web/www/merge.php on line 39

有誰有一個想法，代碼可能會出錯（如果有的話）？我一直盯着這個好一個小時。

<?php 

$array = array(8,1,2,5,6,7); 
print_array($array); 
merge_sort($array); 
print_array($array); 

function merge_sort(&$list){ 
    if(count($list) <= 1){ 
     return $list; 
    } 

    $left = array(); 
    $right = array(); 

    $middle = (int) (count($list)/2); 

    // Make left 
    for($i=0; $i < $middle; $i++){ 
     $left[] = $list[$i]; 
    } 

    // Make right 
    for($i = $middle; $i < count($list); $i++){ 
     $right[] = $list[$i]; 
    } 

    // Merge sort left & right 
    merge_sort($left); 
    merge_sort($right); 

    // Merge left & right 
    return merge($left, $right); 
} 

function merge(&$left, &$right){ 
    $result = array(); 

    while(count($left) > 0 || count(right) > 0){ 
     if(count($left) > 0 && count(right) > 0){ 
      if($left[0] <= $right[0]){ 
       $result[] = array_shift($left); 
      } else { 
       $result[] = array_shift($right); 
      } 
     } elseif (count($left) > 0){ 
      $result[] = array_shift($left); 
     } elseif (count($right) > 0){ 
      $result[] = array_shift($right); 
     } 
    } 

    print_array($result);exit; 

    return $result; 
} 

function print_array($array){ 
    echo "<pre>"; 
    print_r($array); 
    echo "<br/>"; 
    echo "</pre>"; 
} 

?> 

Answer 1

在你merge功能，可以調用次數上right而不是$right。 PHP假設這是一個字符串常量（至少在5.3.9中），並且將其轉換爲始終有一個元素的數組。所以count(right)總是一個，你永遠不會退出第一次合併。

Answer 2

試試這種方法。切片，而不是移動它。

另外，在同時爲merge功能循環，你需要做的和&&比較，而不是 的||

function mergeSort($array) 
{ 
    if(count($array) == 1) 
    { 
     return $array; 
    } 

    $mid = count($array)/2; 
    $left = array_slice($array, 0, $mid); 
    $right = array_slice($array, $mid); 
    $left = mergeSort($left); 
    $right = mergeSort($right); 

    return merge($left, $right); 
} 


function merge($left, $right) 
{ 
    $res = array(); 

    while (count($left) > 0 && count($right) > 0) 
    { 
     if($left[0] > $right[0]) 
     { 
      $res[] = $right[0]; 
      $right = array_slice($right , 1); 
     } 
     else 
     { 
      $res[] = $left[0]; 
      $left = array_slice($left, 1); 
     } 
    } 

    while (count($left) > 0) 
    { 
     $res[] = $left[0]; 
     $left = array_slice($left, 1); 
    } 

    while (count($right) > 0) 
    { 
     $res[] = $right[0]; 
     $right = array_slice($right, 1); 
    } 

    return $res; 
} 

Answer 3

看看這個，算法已經實現了，使用array_push和array splice而不是array_shift。

http://www.codecodex.com/wiki/Merge_sort#PHP 

Answer 4

<?php 

        ################### 
        #merge sort in php# 
        ################### 
$ar=array(2,5,4,3); 
print_r($ar); 
echo "<br/>"; 
$sar=ms($ar); 
print_r($sar); 
echo "<br/>"; 
function ms($tar) 
{ 
$size=count($tar); 
if($size<=1) 
{ 
    print_r($tar); 
    echo "<br/>"; 
    return $tar; 
} 
else 
{ 
    $middle=(int)($size/2); 
    for($i=0;$i<$middle;$i++) 
    { 
     $left[$i]=$tar[$i]; 
    } 
    for($i=$middle,$j=0;$i<$size;$i++,$j++) 
    { 
     $right[$j]=$tar[$i]; 
    } 
    $tl=ms($left); 
    $tr=ms($right); 
    $ma=merge($tl,$tr); 

    return $ma; 
} 
} 
function merge($l,$r) 
{ 

$sizel=count($l); 
$sizer=count($r); 
$j=0; 
while(($sizel>0)||($sizer>0)) 
{ 
    if(($sizel>0) && ($sizer>0)) 
    { 
     if($l[0]<=$r[0]) 
     { 
      $result[$j]=array_shift($l); 
      $j++; 
     } 
     else 
     { 
      $result[$j]=array_shift($r); 
      $j++; 
     } 

    } 
    else if($sizel>0) 
    { 
     $result[$j]=array_shift($l);  
     $j++; 
    } 
    else 
    { 
     $result[$j]=array_shift($r); 
     $j++; 
    } 
    $sizel=count($l); 
    $sizer=count($r); 
} 
    return $result; 
} 
?> 

Answer 5

你歸併排序參考

function merge_sort(&$list) 

接受一個列表，所以你需要爲它分配新的合併和排序的列表。因此，而不是

return merge($left, $right); 

做

$list = $this->merge($left, $right); 

應該這樣做，只是刪除出口和固定計數變量

Answer 6

我實現歸併排序這樣

function mergeSort($Array) 
{ 
    $len = count($Array); 
    if($len==1){ 
     return $Array; 
    } 
    $mid = (int)$len/2; 
    $left = mergeSort(array_slice($Array, 0, $mid)); 
    $right = mergeSort(array_slice($Array, $mid)); 
    return merge($left, $right); 
} 

function merge($left, $right) 
{ 


    $combined = []; 
    $totalLeft = count($left); 
    $totalRight = count($right); 
    $rightIndex = $leftIndex=0; 
    while ($leftIndex < $totalLeft && $rightIndex < $totalRight) { 
     if ($left[$leftIndex] > $right[$rightIndex]) { 
      $combined[]=$right[$rightIndex]; 
      $rightIndex++; 
     }else { 
      $combined[] =$left[$leftIndex]; 
      $leftIndex++; 
     } 
    } 
    while($leftIndex<$totalLeft){ 
     $combined[]=$left[$leftIndex]; 
     $leftIndex++; 
    } 
    while ($rightIndex<$totalRight){ 
     $combined[] =$right[$rightIndex]; 
     $rightIndex++; 
    } 
    return $combined; 
}