PHP 實現經典基礎算法：菱形打印、冒泡排序、楊輝三角、插入排序、快速排序、二分查找、數組合併、遞歸數學建模

算法是程式的靈魂。本文用 PHP 實現 8 個經典基礎算法，涵蓋輸出圖形、排序、查找、數學建模，每個算法附思路解析、完整代碼、複雜度分析與優化方向，適合面試複習與教學演示。

1. 打印菱形（嵌套循環控制空格與星號）

<?php
function printDiamond($n) {
    // 上半部含中線
    for ($i = 0; $i < $n; $i++) {
        echo str_repeat(' ', $n - $i - 1);
        echo str_repeat('*', 2 * $i + 1);
        echo "\n";
    }
    // 下半部
    for ($i = $n - 2; $i >= 0; $i--) {
        echo str_repeat(' ', $n - $i - 1);
        echo str_repeat('*', 2 * $i + 1);
        echo "\n";
    }
}
printDiamond(4);
/*
   *
  ***
 *****
*******
 *****
  ***
   *
*/

2. 冒泡排序（雙層循環相鄰交換）

function bubbleSort(array $arr) {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $swapped = false;
        for ($j = 0; $j < $n - 1 - $i; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                [$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
                $swapped = true;
            }
        }
        if (!$swapped) break; // 優化：已有序提前結束
    }
    return $arr;
}
// O(N²) 穩定排序

3. 楊輝三角（二維數組動態規劃）

function yanghuiTriangle($rows) {
    $triangle = [];
    for ($i = 0; $i < $rows; $i++) {
        $triangle[$i][0] = 1;
        $triangle[$i][$i] = 1;
        for ($j = 1; $j < $i; $j++) {
            $triangle[$i][$j] = $triangle[$i-1][$j-1] + $triangle[$i-1][$j];
        }
    }
    return $triangle;
}
// 輸出
foreach (yanghuiTriangle(6) as $row) {
    echo implode(' ', $row) . "\n";
}
/*
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
*/

4. 有序數組插入元素（線性查找 + 後移）

function insertSorted(array $arr, $val) {
    $n = count($arr);
    if ($n === 0 || $val >= $arr[$n-1]) {
        $arr[] = $val;
        return $arr;
    }
    for ($i = 0; $i < $n; $i++) {
        if ($val <= $arr[$i]) {
            array_splice($arr, $i, 0, $val);
            break;
        }
    }
    return $arr;
}
// O(N) 時間，O(1) 額外空間（原地修改）

5. 快速排序（分治遞歸）

function quickSort(array $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));
}
// 平均 O(N log N)，最壞 O(N²)，不穩定
// 優化：三數取中法選 pivot、小數組改插入排序、尾遞歸消除

6. 二分查找（有序數組前提）

function binarySearch(array $arr, $target) {
    $low = 0;
    $high = count($arr) - 1;
    while ($low <= $high) {
        $mid = (($low + $high) >> 1);
        if ($arr[$mid] === $target) return $mid;
        if ($arr[$mid] < $target) $low = $mid + 1;
        else $high = $mid - 1;
    }
    return -1; // 未找到
}
// O(log N) 時間，O(1) 空間

7. 多數組合併（不使用 array_merge）

function mergeArrays() {
    $args = func_get_args();
    $result = [];
    foreach ($args as $arr) {
        if (!is_array($arr)) continue;
        foreach ($arr as $val) {
            $result[] = $val;
        }
    }
    return $result;
}
// 等價於 array_merge(...$args) 但展示底層邏輯

8. 母牛生育問題（遞歸數學建模）

/*
規則：1隻母牛，4歲開始每年生1隻（同規則），15歲絕育，20歲死亡。
求 n 年後總數。
*/
function cowCount($year) {
    static $cows = []; // 緩存各年齡牛數
    if ($year <= 0) return 1;

    // 年齡分布模擬
    $ages = array_fill(0, 21, 0); // 索引=年齡，值=數量
    $ages[0] = 1; // 初始1隻0歲

    for ($y = 1; $y <= $year; $y++) {
        $newborn = 0;
        // 4-14歲生育
        for ($age = 4; $age <= 14; $age++) {
            $newborn += $ages[$age];
        }
        // 年齡增長（逆序避免覆蓋）
        for ($age = 20; $age >= 1; $age--) {
            $ages[$age] = $ages[$age - 1];
        }
        $ages[0] = $newborn;
        // 20歲死亡（ages[20] 已在下一輪被覆蓋或自然移出）
    }
    return array_sum($ages);
}
// 動態規劃 O(n) 時間，O(1) 空間（固定21長度數組）

算法複雜度總結表