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

前言

雖然 PHP 內建 sort()/usort()/array_search() 效能遠優於手寫演算法，但理解經典演算法邏輯有助於面試、教學與特定場景客製化（如自訂比較器、外部排序）。

1. 冒泡排序

時間複雜度 O(n²)，穩定排序，適合教學或極小資料集（<50 筆）。

<?php
/**
 * 冒泡排序（由小到大）
 * @param array $array 參考傳遞，直接修改原陣列
 * @return array 排序後陣列
 */
function bubble_sort(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]];
                $swapped = true;
            }
        }
        // 提前結束優化：若無交換代表已有序
        if (!$swapped) break;
    }
    return $array;
}

// 測試
$arr = [64, 34, 25, 12, 22, 11, 90];
bubble_sort($arr);
var_dump($arr); // [11, 12, 22, 25, 34, 64, 90]
?>

2. 二分查找

前提：陣列必須已排序。時間複雜度 O(log n)。

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

/** 迭代版（避免遞迴深度限制） */
function binary_search_iterative(array $array, $key) {
    $low = 0;
    $high = count($array) - 1;
    
    while ($low <= $high) {
        $mid = (int)(($low + $high) / 2);
        if ($array[$mid] == $key) return $mid;
        if ($key < $array[$mid]) {
            $high = $mid - 1;
        } else {
            $low = $mid + 1;
        }
    }
    return -1;
}

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

3. 順序查找

無需排序，時間複雜度 O(n)，適合無序小資料集。

<?php
/**
 * 順序查找（哨兵法優化）
 * @param array $array 陣列
 * @param mixed $key   目標值
 * @return int  索引或 -1
 */
function sequential_search(array $array, $key) {
    $n = count($array);
    if ($n === 0) return -1;
    
    // 哨兵：將目標值放在陣列末尾，省去邊界檢查
    $last = $array[$n - 1];
    $array[$n - 1] = $key;
    
    $i = 0;
    while ($array[$i] != $key) {
        $i++;
    }
    
    // 還原
    $array[$n - 1] = $last;
    
    // 判斷是否真找到
    if ($i < $n - 1 || $last == $key) {
        return $i;
    }
    return -1;
}

// 測試
$arr = [64, 34, 25, 12, 22, 11, 90];
echo sequential_search($arr, 25); // 2
?>

4. 二維陣列多鍵值排序

實務最常用：依指定欄位（支援多欄位、升降冪）排序資料集。

<?php
/**
 * 二維陣列多欄位排序
 *
 * @param array  $data   待排序陣列
 * @param string|array $keys  排序鍵（單一字串或多鍵陣列）
 * @param int|array $order   SORT_ASC/SORT_DESC，或對應陣列
 * @param int    $flags  排序旗標（SORT_REGULAR/SORT_NUMERIC/SORT_STRING）
 * @return array 排序後新陣列（不修改原陣列）
 */
function array_multisort_assoc(array $data, $keys, $order = SORT_ASC, $flags = SORT_REGULAR) {
    if (empty($data)) return $data;
    
    // 正規化參數為陣列
    $keys  = (array)$keys;
    $orders = (array)$order;
    $flags  = (array)$flags;
    
    // 建立排序用的鍵值陣列
    $sortArrays = [];
    foreach ($keys as $i => $key) {
        $sortArrays[] = array_column($data, $key);
        $sortArrays[] = $orders[$i] ?? SORT_ASC;
        $sortArrays[] = $flags[$i] ?? SORT_REGULAR;
    }
    // 最後加入原陣列索引保證穩定排序
    $sortArrays[] = array_keys($data);
    
    // array_multisort 會修改傳入的陣列，故先複製
    $dataCopy = $data;
    $sortArrays[] = &$dataCopy;
    
    call_user_func_array('array_multisort', $sortArrays);
    return $dataCopy;
}

// === 使用範例 ===
$users = [
    ['id'=>1, 'name'=>'張三', 'age'=>25, 'score'=>88],
    ['id'=>2, 'name'=>'李四', 'age'=>30, 'score'=>92],
    ['id'=>3, 'name'=>'王五', 'age'=>25, 'score'=>95],
    ['id'=>4, 'name'=>'趙六', 'age'=>28, 'score'=>88],
];

// 先按 age 升序，再按 score 降序
$sorted = array_multisort_assoc($users, ['age', 'score'], [SORT_ASC, SORT_DESC]);
/* 結果：
[
    ['id'=>1, 'age'=>25, 'score'=>88],  // age 25, score 88
    ['id'=>3, 'age'=>25, 'score'=>95],  // age 25, score 95 (較高在前)
    ['id'=>4, 'age'=>28, 'score'=>88],
    ['id'=>2, 'age'=>30, 'score'=>92],
]
*/
print_r($sorted);
?>

PHP 內建函式對照表（實務請直接使用）

效能提醒

• 資料量 > 1,000 筆請務必使用內建函式（C 實作，快 10-100 倍）。
• 手寫演算法僅供教學、面試、或極特殊邏輯（如外部排序、流式處理）使用。
• PHP 7+ spaceship operator (<=>) 讓 usort 寫法極簡潔：usort($arr, fn($a,$b) => $a['age'] <=> $b['age'])。