資料結構與演算法是程式設計的核心內功。PHP 雖非系統級語言,但理解經典演算法的 PHP 實現有助於面試、教學與特定場景優化。本文提供四種基礎演算法的標準實現與解析。
時間複雜度: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]
?>
前提:陣列必須已排序 | 時間複雜度: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
?>
時間複雜度: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
?>
應用場景:資料庫查詢結果排序、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() |
sort()、usort()、array_multisort()(C 底層實現,效能遠超 PHP 代碼)array_search() 或建立索引陣列 array_flip() 達到 O(1)ORDER BY, INDEX)