<?php
function quickSort($arr) {
    if (count($arr) <= 1) {
        return $arr;
    }
    
    $pivot = $arr[0];
    $left = $right = [];
    
    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    
    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

// 测试
$numbers = [64, 34, 25, 12, 22, 11, 90];
echo "原始数组: " . implode(', ', $numbers) . "\n";
echo "快速排序: " . implode(', ', quickSort($numbers)) . "\n";
?>

<?php
function binarySearch($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;
    
    while ($left <= $right) {
        $mid = floor(($left + $right) / 2);
        
        if ($arr[$mid] == $target) {
            return $mid; // 找到目标，返回索引
        }
        
        if ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }
    
    return -1; // 未找到
}

// 测试（数组必须已排序）
$sortedArray = [2, 5, 8, 12, 16, 23, 38, 45, 67];
$target = 23;
$result = binarySearch($sortedArray, $target);

echo "在数组 [" . implode(', ', $sortedArray) . "] 中查找 $target\n";
echo "结果索引: " . ($result !== -1 ? $result : "未找到") . "\n";
?>

<?php
// 递归版本（简单但效率低）
function fibonacciRecursive($n) {
    if ($n <= 1) {
        return $n;
    }
    return fibonacciRecursive($n - 1) + fibonacciRecursive($n - 2);
}

// 动态规划版本（高效）
function fibonacciDP($n) {
    if ($n <= 1) {
        return $n;
    }
    
    $dp = [0, 1];
    for ($i = 2; $i <= $n; $i++) {
        $dp[$i] = $dp[$i - 1] + $dp[$i - 2];
    }
    
    return $dp[$n];
}

// 测试
$n = 10;
echo "斐波那契数列前{$n}项:\n";
for ($i = 0; $i < $n; $i++) {
    echo fibonacciDP($i) . " ";
}
echo "\n";
?>

<?php
function bfs($graph, $start) {
    $visited = [];
    $queue = new SplQueue();
    
    $visited[$start] = true;
    $queue->enqueue($start);
    $result = [];
    
    while (!$queue->isEmpty()) {
        $vertex = $queue->dequeue();
        $result[] = $vertex;
        
        foreach ($graph[$vertex] as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $queue->enqueue($neighbor);
            }
        }
    }
    
    return $result;
}

// 测试
$graph = [
    'A' => ['B', 'C'],
    'B' => ['A', 'D', 'E'],
    'C' => ['A', 'F'],
    'D' => ['B'],
    'E' => ['B', 'F'],
    'F' => ['C', 'E']
];

echo "BFS遍历结果: " . implode(' -> ', bfs($graph, 'A')) . "\n";
?>

<?php
function bubbleSort($arr) {
    $n = count($arr);
    
    for ($i = 0; $i < $n - 1; $i++) {
        $swapped = false;
        
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                // 交换元素
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
                $swapped = true;
            }
        }
        
        // 如果没有交换，说明已经排序完成
        if (!$swapped) {
            break;
        }
    }
    
    return $arr;
}

// 测试
$numbers = [64, 34, 25, 12, 22, 11, 90];
echo "冒泡排序: " . implode(', ', bubbleSort($numbers)) . "\n";
?>

<?php
function maxSubArraySum($arr) {
    $maxSoFar = $arr[0];
    $maxEndingHere = $arr[0];
    
    for ($i = 1; $i < count($arr); $i++) {
        $maxEndingHere = max($arr[$i], $maxEndingHere + $arr[$i]);
        $maxSoFar = max($maxSoFar, $maxEndingHere);
    }
    
    return $maxSoFar;
}

// 测试
$array = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
echo "数组: " . implode(', ', $array) . "\n";
echo "最大子数组和: " . maxSubArraySum($array) . "\n"; // 输出: 6
?>

<?php
function isPrime($n) {
    if ($n <= 1) return false;
    if ($n <= 3) return true;
    if ($n % 2 == 0 || $n % 3 == 0) return false;
    
    for ($i = 5; $i * $i <= $n; $i += 6) {
        if ($n % $i == 0 || $n % ($i + 2) == 0) {
            return false;
        }
    }
    
    return true;
}

// 测试
$numbers = [2, 3, 4, 17, 25, 29];
foreach ($numbers as $num) {
    echo "$num 是" . (isPrime($num) ? "素数" : "非素数") . "\n";
}
?>