PHP 算法实战全景

PHP 8 在算法实现上结合了直观的数组操作与强类型声明：

• 分治排序：利用 foreach 与 array_merge 编写纯函数式快速排序。
• 状态压缩动态规划：利用 array_fill 预分配紧凑状态数组。

---

📊 算法专题与复杂度

算法专题	典型问题 / 算法	核心思想	时间复杂度	空间复杂度
排序	Functional QuickSort / usort	分治递归 / 内置 C 快速排序	$O(n \log n)$	$O(n)$
动态规划	0/1 背包问题	1D 数组倒序状态转移	$O(N \cdot W)$	$O(W)$

---

1. 快速排序算法 (QuickSort)

<?php
function quickSort(array $arr): array {
    if (count($arr) <= 1) return $arr;
    $pivot = $arr[intdiv(count($arr), 2)];
    $left = [];
    $equal = [];
    $right = [];
    foreach ($arr as $v) {
        if ($v < $pivot) $left[] = $v;
        elseif ($v > $pivot) $right[] = $v;
        else $equal[] = $v;
    }
    return array_merge(quickSort($left), $equal, quickSort($right));
}

echo "=== PHP Functional QuickSort ===\n";
$data = [64, 25, 12, 22, 11];
$sorted = quickSort($data);
assert($sorted === [11, 12, 22, 25, 64]);
echo "Sorted: " . implode(", ", $sorted) . "\n";
echo "PHP QuickSort tests passed successfully.\n";

🐳 Docker Verified📋php:8.3-alpine

Exit Code: 0

=== PHP Functional QuickSort ===
Sorted: 11, 12, 22, 25, 64
PHP QuickSort tests passed successfully.

---

2. 动态规划：0/1 背包问题

<?php
function knapsack(int $W, array $weights, array $values): int {
    $dp = array_fill(0, $W + 1, 0);
    $n = count($weights);
    for ($i = 0; $i < $n; $i++) {
        for ($w = $W; $w >= $weights[$i]; $w--) {
            $dp[$w] = max($dp[$w], $dp[$w - $weights[$i]] + $values[$i]);
        }
    }
    return $dp[$W];
}

echo "=== PHP 0/1 Knapsack DP ===\n";
$weights = [2, 3, 4, 5];
$values = [3, 4, 5, 6];
$maxVal = knapsack(5, $weights, $values);
assert($maxVal === 7);
echo "Max Knapsack Value: $maxVal\n";
echo "PHP Knapsack DP tests passed successfully.\n";

🐳 Docker Verified📋php:8.3-alpine

Exit Code: 0

=== PHP 0/1 Knapsack DP ===
Max Knapsack Value: 7
PHP Knapsack DP tests passed successfully.