这个快速排序功能有什么问题 - What's wrong with this quicksort function?

What's wrong with this quicksort function?

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;

很简单。你得到的几乎是无限的递归。

原因是您没有从子数组中排除枢轴点。所以$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;
    }
}