PHP 選擇排序算法深度解析與代碼實現

選擇排序通過重複「選擇極值」來排序，邏輯簡單但效率固定。本文詳細拆解其降序排列過程，並給出標準 PHP 實現代碼。

算法邏輯：每輪鎖定一個最大值

仍以 [2, 6, 3, 9] 降序為例：

• 第 1 輪：假設索引 0 為最大，依次與索引 1~3 比較。發現 9 最大，交換索引 0 和 3 → [9, 6, 3, 2]（注意：原文過程中有多次交換，最終結果一致）。
• 第 2 輪：在剩餘 [6, 3, 2] 中選最大，6 已在首位，無需交換。
• 第 3 輪：在 [3, 2] 中選最大，3 在首位，完成。

共需 n-1 輪，每輪確定一個位置的最終值。

PHP 標準實現

<?php
/**
 * 選擇排序（降序）
 * @param array &$arr 引用傳參
 * @return array 排序後的數組
 */
function selectSort(&$arr) {
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) { // 只需 n-1 輪
        $maxIdx = $i; // 假設當前索引為最大值位置
        for ($j = $i + 1; $j < $len; $j++) {
            if ($arr[$j] > $arr[$maxIdx]) {
                $maxIdx = $j; // 記錄最大值索引
            }
        }
        // 單次交換，減少寫入操作
        if ($maxIdx !== $i) {
            $temp = $arr[$i];
            $arr[$i] = $arr[$maxIdx];
            $arr[$maxIdx] = $temp;
        }
    }
    return $arr;
}

// 測試
$myarr = array(2, 6, 3, 9);
selectSort($myarr);
echo '<pre>';
print_r($myarr); // Array ( [0] => 9 [1] => 6 [2] => 3 [3] => 2 )
?>

關鍵優化點

• 記錄索引而非值：用 $maxIdx 追蹤最大值位置，最後只交換一次，優於原文每次比較都交換的寫法。
• 外層循環 $len - 1：最後一個元素自然就位，無需額外輪次。
• 時間複雜度固定為 O(n²)，無論數據分佈。空間複雜度 O(1)。不穩定排序（相等元素相對位置可能改變）。

對比插入排序

選擇排序寫操作少（最多 n-1 次交換），適合寫入成本高的存儲介質。但插入排序在近乎有序時接近 O(n)，實際應用更靈活。PHP 開發中優先使用內建 rsort()（基於快速排序），僅在教學或極特殊場景手寫排序。