這個快速排序功能有什麼問題？

Question

function quick($a) { 
    if (count($a) < 2) return $a; 
    $l = []; 
    $r = []; 
    $pivot = $a[0]; 
    foreach ($a as $val) { 
     if ($val > $pivot) { 
      $r[] = $val; 
     } else { 
      $l[] = $val; 
     } 
    } 
    return array_merge(quick($l), [$pivot], quick($r)); 
} 

print_r(quick($a)); 

我得到這個錯誤：

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 72 bytes) in /Applications/XAMPP/xamppfiles/htdocs/sort.php on line 46 

46號線是$l[] = $val;

Answer 1

這很簡單。你會得到近乎無限的遞歸。

的原因是，你不排除從子陣列的支點。所以$l將永遠包含它。如果$pivot是不是數組中最小的值，你會無限地與空$r陣列，並複製到$a遞歸$l ...

相反，你需要調整，如果條件並期待在轉動鑰匙：

$pivot = $a[0]; 
foreach ($a as $key => $val) { 
    if ($key === 0) { 
     continue; // pivot 
    } elseif ($val > $pivot) { 
     $r[] = $val; 
    } else { 
     $l[] = $val; 
    } 
}