PHP 七大經典排序算法實現與性能分析實戰指南

PHP 七大經典排序算法實現與性能分析實戰指南

排序算法是計算機科學基石，PHP 開發者雖多用內建 sort() 等函數，但理解底層原理對優化業務邏輯、面試、處理特殊數據結構至關重要。本文提供 7 種經典算法的 PHP 實現、複雜度分析與選型指南。

一、算法複雜度總覽

二、PHP 完整實現代碼

1. 直接插入排序

function insertSort(array $arr): array {
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        if ($arr[$i-1] > $arr[$i]) {
            $tmp = $arr[$i];
            for ($j = $i-1; $j >= 0 && $arr[$j] > $tmp; $j--) {
                $arr[$j+1] = $arr[$j];
            }
            $arr[$j+1] = $tmp;
        }
    }
    return $arr;
}

2. 冒泡排序

function bubbleSort(array $arr): array {
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $swapped = false;
        for ($j = 0; $j < $len - $i; $j++) {
            if ($arr[$j] > $arr[$j+1]) {
                [$arr[$j], $arr[$j+1]] = [$arr[$j+1], $arr[$j]];
                $swapped = true;
            }
        }
        if (!$swapped) break;  // 優化：提前結束
    }
    return $arr;
}

3. 簡單選擇排序

function selectSort(array $arr): array {
    $len = count($arr);
    for ($i = 0; $i < $len; $i++) {
        $minIdx = $i;
        for ($j = $i+1; $j < $len; $j++) {
            if ($arr[$j] < $arr[$minIdx]) $minIdx = $j;
        }
        if ($minIdx !== $i) {
            [$arr[$i], $arr[$minIdx]] = [$arr[$minIdx], $arr[$i]];
        }
    }
    return $arr;
}

4. 希爾排序

function shellSort(array $arr): array {
    $len = count($arr);
    for ($gap = (int)($len/2); $gap > 0; $gap = (int)($gap/2)) {
        for ($i = $gap; $i < $len; $i++) {
            $tmp = $arr[$i];
            for ($j = $i; $j >= $gap && $arr[$j-$gap] > $tmp; $j -= $gap) {
                $arr[$j] = $arr[$j-$gap];
            }
            $arr[$j] = $tmp;
        }
    }
    return $arr;
}

5. 快速排序

function quickSort(array &$arr, int $low, int $high): void {
    if ($low >= $high) return;
    $pivot = $arr[$low];
    $i = $low;
    $j = $high;
    while ($i < $j) {
        while ($i < $j && $arr[$j] >= $pivot) $j--;
        if ($i < $j) $arr[$i++] = $arr[$j];
        while ($i < $j && $arr[$i] <= $pivot) $i++;
        if ($i < $j) $arr[$j--] = $arr[$i];
    }
    $arr[$i] = $pivot;
    quickSort($arr, $low, $i-1);
    quickSort($arr, $i+1, $high);
}

// 入口封裝
function quickSortWrapper(array $arr): array {
    quickSort($arr, 0, count($arr)-1);
    return $arr;
}

6. 堆排序

function heapAdjust(array &$arr, int $start, int $end): void {
    $tmp = $arr[$start];
    for ($j = 2*$start + 1; $j <= $end; $j = 2*$j + 1) {
        if ($j < $end && $arr[$j] < $arr[$j+1]) $j++;
        if ($tmp >= $arr[$j]) break;
        $arr[$start] = $arr[$j];
        $start = $j;
    }
    $arr[$start] = $tmp;
}

function heapSort(array $arr): array {
    $len = count($arr);
    // 建堆
    for ($i = (int)($len/2) - 1; $i >= 0; $i--) {
        heapAdjust($arr, $i, $len-1);
    }
    // 排序
    for ($n = $len-1; $n > 0; $n--) {
        [$arr[0], $arr[$n]] = [$arr[$n], $arr[0]];
        heapAdjust($arr, 0, $n-1);
    }
    return $arr;
}

7. 歸並排序

function merge(array &$src, array &$dest, int $start, int $mid, int $end): void {
    $i = $start; $j = $mid + 1; $k = $start;
    while ($i <= $mid && $j <= $end) {
        $dest[$k++] = ($src[$i] < $src[$j]) ? $src[$i++] : $src[$j++];
    }
    while ($i <= $mid) $dest[$k++] = $src[$i++];
    while ($j <= $end) $dest[$k++] = $src[$j++];
}

function mSort(array &$src, array &$dest, int $start, int $end): void {
    if ($start == $end) {
        $dest[$start] = $src[$start];
        return;
    }
    $mid = (int)(($start + $end) / 2);
    $temp = array();
    mSort($src, $temp, $start, $mid);
    mSort($src, $temp, $mid+1, $end);
    merge($temp, $dest, $start, $mid, $end);
}

function mergeSort(array $arr): array {
    $len = count($arr);
    mSort($arr, $arr, 0, $len-1);
    return $arr;
}

三、性能基準測試（參考數據）

// 測試環境：PHP 8.1, 10萬隨機整數
// 內建 sort()           : 0.012s  (C 級優化，基準)
// quickSortWrapper()    : 0.045s
// heapSort()            : 0.058s
// mergeSort()           : 0.062s
// shellSort()           : 0.180s
// insertSort()          : 12.4s   (O(n²) 明顯)
// selectSort()          : 14.1s
// bubbleSort()          : 15.8s

結論： 實際項目**永遠優先使用內建 sort()/usort()/ksort() 等**，僅在教學、特殊約束（如外部排序、流式排序、自定義比較器無法用 usort 表達）場景手寫算法。

四、工程選型指南

五、PHP 內建排序函數速查

sort($arr)           // 重建索引，值升序
rsort($arr)          // 重建索引，值降序
asort($arr)          // 保持鍵值關聯，值升序
arsort($arr)         // 保持鍵值關聯，值降序
ksort($arr)          // 保持鍵值關聯，鍵升序
krsort($arr)         // 保持鍵值關聯，鍵降序
usort($arr, $cmp)    // 用戶自定義比較，重建索引
uasort($arr, $cmp)   // 用戶自定義比較，保持鍵值
uksort($arr, $cmp)   // 用戶自定義鍵比較，保持鍵值
array_multisort()    // 多維/多陣列排序

六、總結

掌握 7 大經典排序算法的原理、實現與複雜度特徵，是進階工程師的必修課。實際開發中，善用語言內建排序、理解其底層實現（PHP 為 QuickSort + InsertionSort 混合）、根據數據特徵選擇合適比較器，才是解決業務問題的最高效路徑。