PHP 經典排序演算法完整實作：插入、選擇、冒泡、快速、歸並、堆排序

複雜度總覽

1. 插入排序

<?php
function insertionSort(array &$arr): void {
    $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;
    }
}

2. 選擇排序

<?php
function selectionSort(array &$arr): void {
    $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]];
        }
    }
}

3. 冒泡排序 (優化版)

<?php
function bubbleSort(array &$arr): void {
    $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; // 已有序提早結束
    }
}

4. 快速排序 (遞迴 + 三數取中優化)

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

    // 三數取中選 pivot
    $mid = (int)(($low + $high) / 2);
    if ($arr[$low] > $arr[$mid]) [$arr[$low], $arr[$mid]] = [$arr[$mid], $arr[$low]];
    if ($arr[$low] > $arr[$high]) [$arr[$low], $arr[$high]] = [$arr[$high], $arr[$low]];
    if ($arr[$mid] > $arr[$high]) [$arr[$mid], $arr[$high]] = [$arr[$high], $arr[$mid]];
    [$arr[$mid], $arr[$high - 1]] = [$arr[$high - 1], $arr[$mid]];
    $pivot = $arr[$high - 1];

    $i = $low;
    $j = $high - 1;
    while (true) {
        while ($arr[++$i] < $pivot);
        while ($arr[--$j] > $pivot);
        if ($i >= $j) break;
        [$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
    }
    [$arr[$i], $arr[$high - 1]] = [$arr[$high - 1], $arr[$i]];

    quickSort($arr, $low, $i - 1);
    quickSort($arr, $i + 1, $high);
}

5. 歸並排序

<?php
function mergeSort(array $arr): array {
    if (count($arr) <= 1) return $arr;
    $mid = count($arr) >> 1;
    $left  = mergeSort(array_slice($arr, 0, $mid));
    $right = mergeSort(array_slice($arr, $mid));
    return merge($left, $right);
}

function merge(array $left, array $right): array {
    $result = [];
    while ($left && $right) {
        $result[] = ($left[0] <= $right[0]) ? array_shift($left) : array_shift($right);
    }
    return array_merge($result, $left, $right);
}

6. 堆排序 (最大堆，索引從 1 開始好計算)

<?php
function heapSort(array &$arr): void {
    $n = count($arr);
    // 插入哨兵，使索引 1..n 對應堆節點
    array_unshift($arr, null);

    // 建堆：從最後一個非葉節點向前 down-heap
    for ($i = $n >> 1; $i >= 1; $i--) {
        downHeap($arr, $i, $n);
    }

    // 排序：反覆取堆頂與末尾交換，縮小堆範圍
    for ($end = $n; $end > 1; $end--) {
        [$arr[1], $arr[$end]] = [$arr[$end], $arr[1]];
        downHeap($arr, 1, $end - 1);
    }

    // 移除哨兵
    array_shift($arr);
}

function downHeap(array &$arr, int $k, int $n): void {
    while (($child = $k << 1) <= $n) {
        // 選較大的子節點
        if ($child < $n && $arr[$child] < $arr[$child + 1]) $child++;
        if ($arr[$k] >= $arr[$child]) break;
        [$arr[$k], $arr[$child]] = [$arr[$child], $arr[$k]];
        $k = $child;
    }
}

內建函數對比：sort()、usort()

<?php
$data = [3, 1, 4, 1, 5, 9, 2, 6];

sort($data);           // 升序，重建索引
rsort($data);          // 降序

// 關聯陣列保留鍵
$assoc = ['c'=>3, 'a'=>1, 'b'=>2];
asort($assoc);         // 值升序保留鍵
ksort($assoc);         // 鍵升序

// 自定義比較
usort($data, fn($a, $b) => $a <=> $b); // 太空船運算子 (PHP 7+)
uksort($assoc, 'strnatcasecmp'); // 鍵自然排序

效能實測建議

• n < 50：插入排序常比快速排序快 (低常數因子)。
• 一般用途：直接用內建 sort() (C 實作的 QuickSort + InsertionSort 混合)。
• 需穩定排序：usort 不保證穩定，改用 array_multisort 或自行實作歸並。
• 大量資料：不要在 PHP 排序，交給資料庫 ORDER BY 或外部排序工具。