php实现选择排序

选择排序的基本原理

选择排序是一种简单的排序算法，通过不断选择剩余元素中的最小值并交换到已排序部分的末尾。时间复杂度为O(n²)，适合小规模数据排序。

PHP实现选择排序

function selectionSort(array $arr): array {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $minIndex = $i;
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$j] < $arr[$minIndex]) {
                $minIndex = $j;
            }
        }
        if ($minIndex != $i) {
            [$arr[$i], $arr[$minIndex]] = [$arr[$minIndex], $arr[$i]];
        }
    }
    return $arr;
}

代码说明

外层循环控制已排序部分的边界，初始时已排序部分为空。内层循环在未排序部分中查找最小值的索引。找到最小值后与当前边界位置的元素交换。

使用示例

$unsorted = [64, 25, 12, 22, 11];
$sorted = selectionSort($unsorted);
print_r($sorted); // 输出: [11, 12, 22, 25, 64]

优化方向

对于大型数组效率较低，但可以通过以下方式优化：在每次循环中同时查找最小值和最大值，减少交换次数。但时间复杂度仍为O(n²)。