萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 經典演算法實現:冒泡排序、二分查找、順序查找、二維陣列排序

前言

資料結構與演算法是程式設計的核心內功。PHP 雖非系統級語言,但理解經典演算法的 PHP 實現有助於面試、教學與特定場景優化。本文提供四種基礎演算法的標準實現與解析。

1. 冒泡排序

時間複雜度:O(n²) | 空間複雜度:O(1) | 穩定性:穩定

<?php
/**
 * 冒泡排序(由小到大)
 * 
 * @param array $array 輸入陣列(按引用修改)
 * @return array 排序後陣列
 */
function bubble_sort(array $array): array {
    $count = count($array);
    if ($count <= 1) return $array;
    
    for ($i = 0; $i < $count - 1; $i++) {
        $swapped = false;
        // 每輪將最大值「冒泡」到末尾
        for ($j = 0; $j < $count - 1 - $i; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                [$array[$j], $array[$j + 1]] = [$array[$j + 1], $array[$j]]; // PHP 7.1+ 解構賦值
                $swapped = true;
            }
        }
        // 優化:若某輪無交換,說明已有序
        if (!$swapped) break;
    }
    return $array;
}

// 測試
$data = [64, 34, 25, 12, 22, 11, 90];
print_r(bubble_sort($data));
// Output: [11, 12, 22, 25, 34, 64, 90]
?>

2. 二分查找

前提:陣列必須已排序 | 時間複雜度:O(log n) | 空間複雜度:O(log n) 遞迴 / O(1) 迭代

<?php
/**
 * 二分查找(遞迴版)
 * 
 * @param array $array 已排序陣列
 * @param int $low 起始索引
 * @param int $high 結束索引
 * @param mixed $target 目標值
 * @return int 找到返回索引,否則 -1
 */
function binary_search(array $array, int $low, int $high, $target): int {
    if ($low > $high) return -1;
    
    $mid = (int)(($low + $high) / 2);
    
    if ($array[$mid] === $target) {
        return $mid;
    } elseif ($target < $array[$mid]) {
        return binary_search($array, $low, $mid - 1, $target);
    } else {
        return binary_search($array, $mid + 1, $high, $target);
    }
}

/**
 * 二分查找(迭代版,推薦生產使用,避免棧溢位)
 */
function binary_search_iterative(array $array, $target): int {
    $low = 0;
    $high = count($array) - 1;
    
    while ($low <= $high) {
        $mid = (int)(($low + $high) / 2);
        if ($array[$mid] === $target) return $mid;
        if ($target < $array[$mid]) {
            $high = $mid - 1;
        } else {
            $low = $mid + 1;
        }
    }
    return -1;
}

// 測試
$sorted = [11, 12, 22, 25, 34, 64, 90];
echo binary_search_iterative($sorted, 25); // 3
echo binary_search_iterative($sorted, 100); // -1
?>

3. 順序查找

時間複雜度:O(n) | 適用:無序陣列、小規模資料

<?php
/**
 * 順序查找(哨兵法優化版)
 * 
 * @param array $array 輸入陣列
 * @param mixed $target 目標值
 * @return int 找到返回索引,否則 -1
 */
function sequential_search(array $array, $target): int {
    $n = count($array);
    if ($n === 0) return -1;
    
    // 哨兵法:將目標值放在陣列末尾,省去邊界檢查
    $array[] = $target;
    
    for ($i = 0; ; $i++) {
        if ($array[$i] === $target) break;
    }
    
    // 若索引小於原長度,表示在原陣列中找到
    return ($i < $n) ? $i : -1;
}

// 測試
$data = [64, 34, 25, 12, 22];
echo sequential_search($data, 25); // 2
echo sequential_search($data, 99); // -1
?>

4. 二維陣列多鍵值排序

應用場景:資料庫查詢結果排序、API 回應資料處理

<?php
/**
 * 二維陣列多欄位排序(通用版)
 * 
 * @param array $data 待排序資料
 * @param string|array $keys 排序鍵(支援多鍵:['age' => SORT_ASC, 'name' => SORT_DESC])
 * @return array 排序後陣列
 */
function array_multi_sort(array $data, $keys): array {
    if (empty($data) || empty($keys)) return $data;
    
    // 正規化 keys 參數
    if (is_string($keys)) {
        $keys = [$keys => SORT_ASC];
    }
    
    // 建立排序旗標陣列
    $flags = [];
    foreach ($keys as $key => $order) {
        $col = array_column($data, $key);
        $flags[] = $col;
        $flags[] = $order;
    }
    $flags[] = $data; // 最後加入原陣列作為 tie-breaker
    
    // 使用 array_multisort 排序
    array_multisort(...$flags);
    return $data;
}

// 測試資料
$users = [
    ['name' => 'Alice', 'age' => 25, 'score' => 90],
    ['name' => 'Bob', 'age' => 20, 'score' => 85],
    ['name' => 'Charlie', 'age' => 25, 'score' => 95],
    ['name' => 'David', 'age' => 30, 'score' => 80],
];

// 年齡升序,同齡分數降序
$sorted = array_multi_sort($users, [
    'age' => SORT_ASC,
    'score' => SORT_DESC,
]);

print_r($sorted);
/*
結果:
Bob (20, 85)
Alice (25, 90)
Charlie (25, 95)  ← 同齡分數高者在前
David (30, 80)
*/
?>

效能對比與建議

演算法時間複雜度適用場景PHP 內建替代
冒泡排序O(n²)教學、極小資料集(<50)sort(), asort()
二分查找O(log n)大量有序資料查詢無直接替代,需自行實現
順序查找O(n)無序資料、小資料集array_search(), in_array()
二維陣列排序O(n log n)多欄位業務排序array_multisort() + array_column()

生產環境建議

  • 排序:永遠優先使用 PHP 內建 sort()、usort()、array_multisort()(C 底層實現,效能遠超 PHP 代碼)
  • 查找:有序資料用二分查找,無序用 array_search() 或建立索引陣列 array_flip() 達到 O(1)
  • 大數據:超過萬筆資料建議在資料庫層完成排序/查找(ORDER BY, INDEX)
copyright © 萬盛學電腦網 all rights reserved