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

資料結構與演算法是程式設計核心。本文以 PHP 實現四大基礎演算法，含完整代碼、複雜度分析與實務優化建議。

1. 冒泡排序

時間複雜度：O(n²) | 空間複雜度：O(1) | 穩定排序

<?php
/**
 * 冒泡排序 (升序)
 * @param array $array 待排序陣列 (引用修改)
 * @return array 排序後陣列
 */
function bubbleSort(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]];
                $swapped = true;
            }
        }
        // 優化：若無交換提前結束
        if (!$swapped) break;
    }
    return $array;
}

// 使用
$data = [64, 34, 25, 12, 22, 11, 90];
bubbleSort($data);
print_r($data); // [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 binarySearchRecursive(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 binarySearchRecursive($array, $low, $mid - 1, $target);
    } else {
        return binarySearchRecursive($array, $mid + 1, $high, $target);
    }
}

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

// 使用
$sorted = [1, 3, 5, 7, 9, 11, 13, 15];
echo binarySearchIterative($sorted, 7);  // 3
echo binarySearchIterative($sorted, 8);  // -1

3. 順序查找

時間複雜度：O(n) | 空間複雜度：O(1) | 無需排序

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

/**
 * 簡單版 (教學用)
 */
function sequentialSearchSimple(array $array, $target): int {
    foreach ($array as $index => $value) {
        if ($value === $target) return $index;
    }
    return -1;
}

4. 二維陣列多鍵值排序

通用排序函式，支援多欄位、升降序、大小寫不敏感

<?php
/**
 * 二維陣列多欄位排序
 * @param array $data 待排序資料
 * @param array $columns 排序規則 [
 *     ['field' => 'age', 'order' => SORT_ASC, 'flags' => SORT_NUMERIC],
 *     ['field' => 'name', 'order' => SORT_DESC, 'flags' => SORT_STRING | SORT_FLAG_CASE]
 * ]
 * @return array 排序後資料
 */
function arrayMultiSort(array $data, array $columns): array {
    if (empty($data) || empty($columns)) return $data;
    
    $sortArrays = [];
    foreach ($columns as $col) {
        $field = $col['field'];
        $order = $col['order'] ?? SORT_ASC;
        $flags = $col['flags'] ?? SORT_REGULAR;
        
        $values = array_column($data, $field);
        $sortArrays[] = $values;
        $sortArrays[] = $order;
        $sortArrays[] = $flags;
    }
    
    // 保留原始索引關聯
    $sortArrays[] = &$data;
    
    array_multisort(...$sortArrays);
    return $data;
}

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

// 年齡升序、同齡分數降序
$sorted = arrayMultiSort($users, [
    ['field' => 'age', 'order' => SORT_ASC, 'flags' => SORT_NUMERIC],
    ['field' => 'score', 'order' => SORT_DESC, 'flags' => SORT_NUMERIC],
]);

print_r($sorted);
/*
結果：
1. 王五 (25歲, 95.5分)
2. 張三 (25歲, 88.5分)
3. 趙六 (28歲, 88.5分)
4. 李四 (30歲, 92.0分)
*/

PHP 內建排序函式速查

效能建議

• 實務專案：直接使用 PHP 內建 sort()/usort()/array_multisort() (C 實現，極快)
• 大數據量：考慮資料庫 ORDER BY、Redis Sorted Set、Elasticsearch
• 教學/面試：理解冒泡/快速/合併/堆排序原理與複雜度差異
• 二分查找：生產環境用迭代版避免遞迴堆疊溢出