您现在的位置：程式碼之家 >> 編程語言 > >> 網頁程式設計 >> PHP 程式設計 >> PHP 綜合知識

PHP 經典算法大全：排序、查找、遞歸、組合數學實戰精講

編輯：PHP 綜合知識

基礎排序算法

1. 冒泡排序 - O(n²)

function bubbleSort(array &$arr): void {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        for ($j = 0; $j < $n - 1 - $i; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                [$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
            }
        }
    }
}

2. 選擇排序 - O(n²)

function selectionSort(array &$arr): void {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $minIdx = $i;
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$j] < $arr[$minIdx]) $minIdx = $j;
        }
        if ($minIdx !== $i) {
            [$arr[$i], $arr[$minIdx]] = [$arr[$minIdx], $arr[$i]];
        }
    }
}

3. 插入排序 - O(n²)，近乎有序數據 O(n)

function insertionSort(array &$arr): void {
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $key;
    }
}

4. 希爾排序 - O(n log n) 到 O(n²)

function shellSort(array &$arr): void {
    $n = count($arr);
    for ($gap = $n >> 1; $gap > 0; $gap >>= 1) {
        for ($i = $gap; $i < $n; $i++) {
            $temp = $arr[$i];
            $j = $i;
            while ($j >= $gap && $arr[$j - $gap] > $temp) {
                $arr[$j] = $arr[$j - $gap];
                $j -= $gap;
            }
            $arr[$j] = $temp;
        }
    }
}

5. 快速排序 - 平均 O(n log n)，最壞 O(n²)

function quickSort(array &$arr, int $left = 0, int $right = null): void {
    if ($right === null) $right = count($arr) - 1;
    if ($left >= $right) return;
    
    $pivot = $arr[(($left + $right) >> 1)];
    $i = $left;
    $j = $right;
    
    while ($i <= $j) {
        while ($arr[$i] < $pivot) $i++;
        while ($arr[$j] > $pivot) $j--;
        if ($i <= $j) {
            [$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
            $i++;
            $j--;
        }
    }
    
    if ($left < $j) quickSort($arr, $left, $j);
    if ($i < $right) quickSort($arr, $i, $right);
}

6. 歸並排序 - 穩定 O(n log n)

function mergeSort(array $arr): array {
    if (count($arr) <= 1) return $arr;
    
    $mid = count($arr) >> 1;
    $left = mergeSort(array_slice($arr, 0, $mid));
    $right = mergeSort(array_slice($arr, $mid));
    
    return merge($left, $right);
}

function merge(array $left, array $right): array {
    $result = [];
    while ($left && $right) {
        $result[] = ($left[0] <= $right[0]) ? array_shift($left) : array_shift($right);
    }
    return array_merge($result, $left, $right);
}

查找算法

二分查找 - O(log n)，要求有序

function binarySearch(array $arr, $target): int {
    $left = 0;
    $right = count($arr) - 1;
    
    while ($left <= $right) {
        $mid = (($left + $right) >> 1);
        if ($arr[$mid] === $target) return $mid;
        if ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }
    return -1; // 未找到
}

// 遞歸版
function binarySearchRecursive(array $arr, $target, int $left, int $right): int {
    if ($left > $right) return -1;
    $mid = (($left + $right) >> 1);
    if ($arr[$mid] === $target) return $mid;
    return $arr[$mid] < $target 
        ? binarySearchRecursive($arr, $target, $mid + 1, $right)
        : binarySearchRecursive($arr, $target, $left, $mid - 1);
}

經典遞歸問題

楊輝三角

function yanghuiTriangle(int $rows): array {
    $triangle = [];
    for ($i = 0; $i < $rows; $i++) {
        $triangle[$i] = [];
        for ($j = 0; $j <= $i; $j++) {
            if ($j === 0 || $j === $i) {
                $triangle[$i][$j] = 1;
            } else {
                $triangle[$i][$j] = $triangle[$i-1][$j-1] + $triangle[$i-1][$j];
            }
        }
    }
    return $triangle;
}

// 輸出
$triangle = yanghuiTriangle(6);
foreach ($triangle as $row) {
    echo implode(' ', $row) . "\n";
}

斐波那契數列（備忘錄優化）

function fibonacci(int $n, array &$memo = []): int {
    if ($n <= 1) return $n;
    if (isset($memo[$n])) return $memo[$n];
    return $memo[$n] = fibonacci($n - 1, $memo) + fibonacci($n - 2, $memo);
}

// 迭代版 O(n) 空間 O(1)
function fibonacciIter(int $n): int {
    if ($n <= 1) return $n;
    $a = 0; $b = 1;
    for ($i = 2; $i <= $n; $i++) {
        [$a, $b] = [$b, $a + $b];
    }
    return $b;
}

漢諾塔

function hanoi(int $n, string $from, string $to, string $aux): void {
    if ($n === 1) {
        echo "Move disk 1 from {$from} to {$to}\n";
        return;
    }
    hanoi($n - 1, $from, $aux, $to);
    echo "Move disk {$n} from {$from} to {$to}\n";
    hanoi($n - 1, $aux, $to, $from);
}

組合數學與位運算技巧

全排列（字典序）

function permutations(array $arr): array {
    $result = [$arr];
    $n = count($arr);
    
    while (true) {
        // 1. 從右向左找第一個 a[i] < a[i+1]
        $i = $n - 2;
        while ($i >= 0 && $arr[$i] >= $arr[$i + 1]) $i--;
        if ($i < 0) break;
        
        // 2. 從右向左找第一個 a[j] > a[i]
        $j = $n - 1;
        while ($arr[$j] <= $arr[$i]) $j--;
        
        // 3. 交換並反轉後綴
        [$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
        $left = $i + 1;
        $right = $n - 1;
        while ($left < $right) {
            [$arr[$left], $arr[$right]] = [$arr[$right], $arr[$left]];
            $left++; $right--;
        }
        $result[] = $arr;
    }
    return $result;
}

組合生成（位掩碼法）

/**

 * 從 $arr 中選 $k 個元素的所有組合
 * @return array
 */
function combinations(array $arr, int $k): array {
    $n = count($arr);
    $result = [];
    $max = 1 << $n; // 2^n
    
    for ($mask = 0; $mask < $max; $mask++) {
        // 統計 1 的個數
        if (count_bits($mask) !== $k) continue;
        
        $combo = [];
        for ($i = 0; $i < $n; $i++) {
            if ($mask & (1 << $i)) {
                $combo[] = $arr[$i];
            }
        }
        $result[] = $combo;
    }
    return $result;
}

function count_bits(int $n): int {
    $count = 0;
    while ($n) {
        $n &= $n - 1; // 清除最低位 1
        $count++;
    }
    return $count;
}

// 使用
$combos = combinations([1,2,3,4,5], 3); // 10 種組合

實戰綜合案例

牛年求牛問題（動態規劃）

/**

 * 母牛 4 歲生育，每年 1 頭，15 歲絕育，20 歲死亡
 * @param int $years 年數
 * @return int 總頭數
 */
function cowPopulation(int $years): int {
    // 年齡分布：索引 = 年齡，值 = 該年齡牛的數量
    $ages = array_fill(0, 21, 0);
    $ages[0] = 1; // 初始 1 隻 0 歲母牛
    
    for ($year = 1; $year <= $years; $year++) {
        $newborns = 0;
        // 4-14 歲生育
        for ($age = 4; $age <= 14; $age++) {
            $newborns += $ages[$age];
        }
        // 年齡遞增（從大到小避免覆蓋）
        for ($age = 20; $age > 0; $age--) {
            $ages[$age] = $ages[$age - 1];
        }
        $ages[0] = $newborns;
        // 20 歲自然死亡（已通過數組長度隱式處理）
    }
    
    return array_sum($ages);
}

echo cowPopulation(10); // 第 10 年總數

算法複雜度速查表

算法	平均時間	最壞時間	空間	穩定
冒泡	O(n²)	O(n²)	O(1)	✓
選擇	O(n²)	O(n²)	O(1)	✗
插入	O(n²)	O(n²)	O(1)	✓
希爾	O(n^1.3)	O(n²)	O(1)	✗
快速	O(n log n)	O(n²)	O(log n)	✗
歸並	O(n log n)	O(n log n)	O(n)	✓
堆排序	O(n log n)	O(n log n)	O(1)	✗
計數/基數	O(n+k)	O(n+k)	O(n+k)	✓