PHP 常見排序與查找算法實現：冒泡、選擇、插入、快排、二分查找

排序算法

1. 冒泡排序

function bubbleSort(array &$arr) {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $swapped = false;
        for ($j = 0; $j < $n - 1 - $i; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                [$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
                $swapped = true;
            }
        }
        if (!$swapped) break; // 已有序提前退出
    }
}

時間複雜度：O(n²) 最好 O(n)；空間 O(1)；穩定。

2. 選擇排序

function selectionSort(array &$arr) {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $minIdx = $i;
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$j] < $arr[$minIdx]) $minIdx = $j;
        }
        if ($minIdx !== $i) [$arr[$i], $arr[$minIdx]] = [$arr[$minIdx], $arr[$i]];
    }
}

時間複雜度：O(n²)；空間 O(1)；不穩定；交換次數最少 (n-1)。

3. 插入排序

function insertionSort(array &$arr) {
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $key;
    }
}

時間複雜度：O(n²) 最好 O(n)；空間 O(1)；穩定；小數據量/近乎有序時極快。

4. 快速排序（原地分區版）

function quickSort(array &$arr, $left = 0, $right = null) {
    if ($right === null) $right = count($arr) - 1;
    if ($left >= $right) return;

    $pivot = $arr[(int)(($left + $right) / 2)];
    $i = $left; $j = $right;

    while ($i <= $j) {
        while ($arr[$i] < $pivot) $i++;
        while ($arr[$j] > $pivot) $j--;
        if ($i <= $j) {
            [$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
            $i++; $j--;
        }
    }
    if ($left < $j) quickSort($arr, $left, $j);
    if ($i < $right) quickSort($arr, $i, $right);
}

平均 O(n log n)，最壞 O(n²)；空間 O(log n) 棧；不穩定；實際性能通常最優。

5. 快速排序（函數式風格，返回新數組）

function quickSortFunc(array $arr, $order = 'asc') {
    if (count($arr) <= 1) return $arr;
    $pivot = $arr[0];
    $left = $right = [];
    foreach (array_slice($arr, 1) as $v) {
        if (($order === 'asc' && $v <= $pivot) || ($order === 'desc' && $v >= $pivot)) {
            $left[] = $v;
        } else {
            $right[] = $v;
        }
    }
    return array_merge(quickSortFunc($left, $order), [$pivot], quickSortFunc($right, $order));
}

查找算法

1. 線性查找

function linearSearch(array $arr, $target) {
    foreach ($arr as $i => $v) {
        if ($v === $target) return $i;
    }
    return -1;
}

2. 二分查找（前提：有序數組）

function binarySearch(array $arr, $target) {
    $left = 0; $right = count($arr) - 1;
    while ($left <= $right) {
        $mid = (int)(($left + $right) / 2);
        if ($arr[$mid] === $target) return $mid;
        if ($arr[$mid] < $target) $left = $mid + 1;
        else $right = $mid - 1;
    }
    return -1;
}

時間 O(log n)；空間 O(1)；要求數組已排序。

性能基準測試 (PHP 8.1, 10萬隨機整數)

實戰建議

1. 生產代碼直接用 sort()/rsort()/usort()：C 實現、高度優化、支持自定義比較器。
2. 面試/教學：掌握快排分區邏輯、插入排序在近乎有序數據上的優勢。
3. 查找：有序數組用二分，無序用線性或先排序；PHP 中 array_search 內部為線性，in_array 同理。
4. 大數據量：考慮外部排序、資料庫 ORDER BY、Redis 有序集合 (ZSET)。