PHP简单选择排序算法实现与性能分析

拾柒

发布时间：2026-10-14| 5人浏览过

原创

简单选择排序是一种直观的基础排序算法，通过不断从未排序部分选出最小元素并与起始位置交换来完成排序。本文将提供PHP实现的完整代码，解析其核心步骤，并分析其时间与空间复杂度，帮助开发者深入理解该算法的执行效率。

算法原理概述

简单选择排序的核心思想非常直观：假设有一个包含 n 个元素的数组，算法执行 n-1 趟扫描。在第 i 趟（1 <= i <= n）时：

从当前未排序的子数组（即第 i 个到第 n 个记录）中，找出关键字最小的记录。
将该最小记录与未排序部分的第一个记录（即第 i 个位置）进行交换。

通过这种方式，每一趟都能确定一个元素的最终位置，直到所有元素有序排列。相比冒泡排序频繁的相邻交换，选择排序显著减少了数据的移动次数，从而在某种程度上节约了时间。

PHP代码实现

为了实现结构化的代码管理，我们可以将选择排序封装为一个类。以下是具体的PHP实现代码，包含了排序主逻辑和一个辅助的交换函数。

<?php
class Sort {
    /**
     * 简单的选择排序
     *
     * @param array $arr 引用传递，直接修改原数组
     */
    public function selectSort(&$arr) {
        $len = count($arr);
        
        // 遍历每一个位置，确定该位置的最终元素
        for ($i = 0; $i < $len; $i++) {
            $min = $i; // 假设当前位置是最小值的下标
            
            // 在未排序部分中寻找更小的值
            for ($j = $i + 1; $j <= $len - 1; $j++) {
                if ($arr[$min] > $arr[$j]) {
                    $min = $j; // 找到更小的值，更新最小值下标
                }
            }
            
            // 如果找到的最小值不在当前$i位置，则交换
            if ($min != $i) {
                $this->swap($arr[$i], $arr[$min]);
            }
        }
    }

    /**
     * 将两个变量的值进行交换
     */
    private function swap(&$a, &$b) {
        $temp = $a;
        $a = $b;
        $b = $temp;
    }
}

// 测试用例
$arr = array(4, 6, 1, 2, 9, 8, 7, 3, 5);
$test = new Sort();
$test->selectSort($arr);

// 输出排序后的结果
print_r($arr);
?>

代码关键点解析

引用传递 (&)： 在 selectSort 和 swap 方法中，参数使用了引用符号 &。这是为了确保函数内部对数组或变量的修改能直接影响外部原始数据，避免创建不必要的副本，节省内存开销。
外层循环： 控制排序的趟数，从索引 0 到 $len - 1。每一趟结束后，前 i+1 个元素都是有序的。
内层循环： 负责在当前未排序区间（$i+1 到末尾）中查找最小值的索引 $min。
交换条件： 只有当找到的最小值索引 $min 不等于当前待排序位置 $i 时才执行交换操作，避免无效的自我赋值。

性能分析与复杂度

理解选择排序的性能特点对于在实际场景中评估其适用性至关重要。

时间复杂度

简单选择排序的比较次数与数据的初始排列状态无关：

第 1 趟需要比较 n-1 次。
第 2 趟需要比较 n-2 次。
...
第 n-1 趟需要比较 1 次。

总比较次数为等差数列求和：
Total = (n-1) + (n-2) + ... + 1 = n(n-1)/2

因此，无论最好情况（已经有序）还是最坏情况（逆序），其时间复杂度均为 O(n²)。

与冒泡排序的对比

虽然简单选择排序和冒泡排序的时间复杂度同为 O(n²)，但选择排序在实际性能上通常略优于冒泡排序。主要原因在于：
交换次数少： 冒泡排序在每次发现逆序时都会进行相邻交换，最多可能进行 O(n²) 次交换；而选择排序每趟只进行一次交换（仅当最小值不在正确位置时），总共最多进行 n-1 次交换。由于交换操作涉及临时变量赋值，相对比较操作成本更高，减少交换次数意味着节省了相应的处理时间。