萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 選擇排序法實現陣列排序詳解

算法原理

選擇排序 每輪從未排序區選出最大 (或最小) 元素,與未排序區首位元素交換。進行 n-1 輪後完成排序。特點是交換次數少 (最多 n-1 次),但比較次數固定 O(n²)。

逐步執行示意 (由大到小)

原始:[2, 6, 3, 9]

  1. 第 1 輪 (i=0):假設 2 最大,依序與 6、3、9 比較。發現 9 最大,交換 2 與 9 → [9, 6, 3, 2]
  2. 第 2 輪 (i=1):假設 6 最大,與 3、2 比較,6 維持 → [9, 6, 3, 2]
  3. 第 3 輪 (i=2):假設 3 最大,與 2 比較,3 維持 → [9, 6, 3, 2]

PHP 實作

<?php
function selectSort(&$arr) {
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        $maxIdx = $i;
        for ($j = $i + 1; $j < $len; $j++) {
            if ($arr[$j] > $arr[$maxIdx]) { // 由大到小
                $maxIdx = $j;
            }
        }
        if ($maxIdx !== $i) {
            // 交換
            $tmp = $arr[$i];
            $arr[$i] = $arr[$maxIdx];
            $arr[$maxIdx] = $tmp;
        }
    }
}

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

複雜度分析

指標數值
時間複雜度O(n²) (最好/最差/平均皆同)
空間複雜度O(1) 原地排序
比較次數n(n-1)/2
交換次數0 ~ n-1
穩定性不穩定 (相等元素相對位置可能改變)

與插入排序比較

  • 選擇排序交換次數少,適合寫入成本高的儲存體 (如 EEPROM)。
  • 插入排序在近乎有序時極快,選擇排序無此優勢。
  • 兩者皆為 O(n²),實務上大數據量請用 rsort()/arsort()。

教學價值

選擇排序邏輯直觀,適合初學者理解「循環不變式」與「原地交換」概念,也是後續學習堆積排序 的基礎。

copyright © 萬盛學電腦網 all rights reserved