PHP 面試必考演算法總整理：排序、查找、遞歸、檔案遍歷與 URL 解析

PHP 面試必考演算法總整理：排序、查找、遞歸、檔案遍歷與 URL 解析

整理 PHP 面試高頻演算法題目，涵蓋冒泡/快速排序、二分/順序查找、目錄遞歸遍歷、URL 副檔名提取、中文截取無亂碼，附完整程式碼與複雜度分析，助你高效備戰。

一、冒泡排序

思想：相鄰比較、大數後移（或小數前移），每輪將極值「冒泡」到正確位置。
複雜度：時間 O(n²)，空間 O(1)，穩定排序。

<?php
function bubbleSort(array $arr): array {
    $len = count($arr);
    for ($i = 0; $i < $len; $i++) {
        $swapped = false;
        // 每輪減少一次比較，因為最後 $i 個已就位
        for ($j = 0; $j < $len - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) { // 升序
                [$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
                $swapped = true;
            }
        }
        if (!$swapped) break; // 提前結束優化
    }
    return $arr;
}
var_dump(bubbleSort([3, 1, 2])); // [1,2,3]
?>

二、快速排序

思想：選基準，分區（小左大右），遞歸處理子區間。
複雜度：平均 O(n log n)，最差 O(n²)，空間 O(log n)，不穩定。

<?php
function quickSort(array $arr): array {
    $len = count($arr);
    if ($len <= 1) return $arr;

    $pivot = $arr[0];
    $left = $right = [];

    for ($i = 1; $i < $len; $i++) {
        if ($arr[$i] < $pivot) $left[] = $arr[$i];
        else $right[] = $arr[$i];
    }
    return array_merge(quickSort($left), [$pivot], quickSort($right));
}
var_dump(quickSort([3, 1, 2])); // [1,2,3]
?>

三、二分查找

前提：陣列**已排序**（升序）。
複雜度：時間 O(log n)，空間 O(1) 迭代 / O(log n) 遞歸。

<?php
function binarySearch(array $arr, int $target): int {
    $low = 0;
    $high = count($arr) - 1;

    while ($low <= $high) {
        $mid = (int)(($low + $high) / 2);
        if ($arr[$mid] === $target) return $mid;
        if ($target < $arr[$mid]) $high = $mid - 1;
        else $low = $mid + 1;
    }
    return -1;
}
$arr = range(1, 10);
echo binarySearch($arr, 3); // 2 (0-based index)
?>

四、順序查找

適用：無序、小規模資料。
複雜度：時間 O(n)，空間 O(1)。

<?php
function linearSearch(array $arr, $target): int {
    foreach ($arr as $i => $val) {
        if ($val === $target) return $i;
    }
    return -1;
}
?>

五、遞歸遍歷目錄（含子目錄）

<?php
function scanDirRecursive(string $dir): array {
    $result = [];
    $items = scandir($dir);
    foreach ($items as $item) {
        if ($item === '.' || $item === '..') continue;
        $path = $dir . DIRECTORY_SEPARATOR . $item;
        if (is_dir($path)) {
            $result[$item] = scanDirRecursive($path);
        } else {
            $result[] = $item;
        }
    }
    return $result;
}
var_dump(scanDirRecursive('..'));
?>

六、高效提取 URL 副檔名

利用內建 parse_url() + basename() + pathinfo()，避免手寫正則。

<?php
function getExtension(string $url): string {
    $parts = parse_url($url);
    $path = $parts['path'] ?? '';
    return pathinfo($path, PATHINFO_EXTENSION);
}
echo getExtension('https://example.com/abc/de/fg.html.php?id=1'); // php
?>

七、中文截取無亂碼

使用 mb_substr()，需確保 php.ini 載入 mbstring 擴展。

<?php
// 確保內部編碼一致
mb_internal_encoding('UTF-8');

$str = '你好，世界！';
echo mb_substr($str, 0, 3); // 你好，
?>

面試加分技巧

• 主動說明**時間/空間複雜度**與**穩定性**。
• 指出 PHP 內建 sort()、array_search() 等函數的實現原理（C 底層 QuickSort/Hash）。
• 大數據量建議**資料庫索引/全文搜尋**，而非 PHP 陣列查找。
• 遞歸深度注意 xdebug.max_nesting_level 限制，必要時改寫為迭代。