PHP 經典排序與查找算法實現：冒泡、快速、二分查找、二維數組去重

一、冒泡排序 - 教學入門級

時間複雜度 O(n²)，空間 O(1)，穩定排序。僅適合極小數據量或教學演示。

<?php
function bubbleSort(array $arr): array
{
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $swapped = false;
        for ($j = 0; $j < $n - $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;
}
?>

二、快速排序 - 實用高效

平均 O(n log n)，最壞 O(n²)，不穩定。PHP 內置 sort() 底層即為快速排序變體（Zend QSort）。

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

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

    for ($i = 1; $i < $n; $i++) {
        if ($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

// 測試
$data = [1, 5, 3, 4, 12, 10, 8];
echo "冒泡: " . implode(',', bubbleSort($data)) . "\n";
echo "快速: " . implode(',', quickSort($data)) . "\n";
// 輸出: 1,3,4,5,8,10,12
?>

生產建議：直接使用 sort()、rsort()、usort() 等內置函數，C 級性能、處理邊界情況完善。

三、二分查找 - 有序數組專用

前提：數組已排序。時間 O(log n)，空間 O(log n) 遞歸 / O(1) 迭代。

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

    $mid = (int)(($low + $high) / 2);
    if ($arr[$mid] == $target) return $mid;
    if ($target < $arr[$mid]) return binarySearch($arr, $target, $low, $mid - 1);
    return binarySearch($arr, $target, $mid + 1, $high);
}

// 迭代版（推薦，無棧溢出風險）
function binarySearchIter(array $arr, $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 = [4, 5, 7, 8, 9, 10, 12];
echo binarySearchIter($arr, 8); // 3 (索引)
?>

四、二維數組去重 - 實用技巧

核心思路：降維 → 唯一值 → 還原。使用 serialize() 或 json_encode() 比 implode() 更安全（避免分隔符衝突）。

<?php
function arrayUnique2D(array $arr, array $keys = null): array
{
    $temp = [];
    foreach ($arr as $item) {
        // 序列化整行，保證鍵值順序一致
        $temp[] = serialize($item);
    }
    $temp = array_unique($temp); // 去重
    $result = [];
    foreach ($temp as $v) {
        $result[] = unserialize($v);
    }
    // 可選：重新索引並指定鍵名
    if ($keys) {
        $result = array_map(function($v) use ($keys) {
            return array_combine($keys, array_values($v));
        }, $result);
    }
    return array_values($result); // 重置索引
}

// 測試
$data = [
    ['a' => 1, 'b' => 2, 'c' => 3],
    ['a' => 1, 'b' => 2, 'c' => 3],
    ['a' => 4, 'b' => 5, 'c' => 6],
];
print_r(arrayUnique2D($data, ['a','b','c']));
/*
Array
(
    [0] => Array ( [a] => 1 [b] => 2 [c] => 3 )
    [1] => Array ( [a] => 4 [b] => 5 [c] => 6 )
)
*/
?>

性能對比總結