PHP 选择排序实现：从原理到代码的逐步拆解

算法思路

每轮从未排序区选出极值（最大/最小），与区首元素交换。共 n-1 趟。

示例 [2,6,3,9] 降序：

1. 假设 0 位最大，依次与 1~3 比较交换 → [9,2,3,6]
2. 假设 1 位最大，与 2~3 比较交换 → [9,6,2,3]
3. 假设 2 位最大，与 3 比较交换 → [9,6,3,2]

PHP 实现（引用传参原地排序）

<?php
function selectSort(array &$arr): array {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $maxIdx = $i;
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$j] > $arr[$maxIdx]) {
                $maxIdx = $j;
            }
        }
        if ($maxIdx !== $i) {
            [$arr[$i], $arr[$maxIdx]] = [$arr[$maxIdx], $arr[$i]]; // PHP 7.1+ 解构赋值
        }
    }
    return $arr;
}

$arr = [2, 6, 3, 9];
selectSort($arr);
print_r($arr); // [9, 6, 3, 2]
?>

复杂度分析

优化点

• 双向选择排序：每趟同时选最大和最小，减少约一半循环
• 小规模数据（<50）性能可接受，大数据量建议用快排/归并/内置 rsort()