php - 这个快速排序功能有什么问题？

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...

相反，您需要调整 if 条件并查看枢轴键：

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