PHP 简单选择排序算法实现与解析

排序目标与原理

简单选择排序（Simple Selection Sort）的主要目标是生成一个递增有序的数组。其工作原理如下：

1. 扫描：从当前未排序的起始位置开始，向后扫描直到最后一个元素。
2. 记录最小值：假设当前位置为最小值索引（即 $min=i$），在扫描过程中不断更新发现更小元素的索引。
3. 交换：当扫描结束后，如果记录的最小值索引 $min$ 不等于初始位置 $i$，则说明发现了更小的元素，此时将这两个位置的数值进行交换。
4. 推进：处理下一个位置，重复上述过程，直到所有元素排序完成。

由于需要进行多层嵌套循环比较，该算法的时间复杂度为 $O(n^2)$，适用于数据量较小的场景。

准备条件与参数定义

为了清晰地展示排序的内部机制，我们需要设置以下输入参数和辅助逻辑：

• 输入数据：一个包含整数元素的 PHP 数组，例如：$list = array(4, 3, 2, 1, 5, 7, 3, 7)。
• 函数接口：定义 function sort_simple_selection($list) 接收待排序数组。
• 调试信息：为了便于观察，代码中嵌入了 echo 语句，用于打印每次内层循环结束时的数组状态及找到的最小值位置。

真实操作顺序

第1步：初始化长度检查与外层循环

首先获取数组长度 $len$。若数组为空则直接返回。接着启动外层循环，变量 $i$ 代表当前需要确定的位置（从 0 到 $len-1$）。

入口：函数开始执行。
动作：计算 count($list)，初始化 $i=0$。

第2步：设定基准与内层最小值查找

进入第 $i$ 轮比较时，先假设当前就是最小值的位置，即 $min = $i。随后启动内层循环，变量 $j$ 从 $i + 1$ 开始一直遍历到数组末尾。

参数：$min$ (初始值为 $i$)，$j$ (从 $i+1$ 至 $len-1$)。
比较逻辑：if($list[$j] < $list[$min])，一旦发现比当前记录更小值，立即更新 $min = $j。

第3步：输出中间状态

在内层循环每轮结束后（或整个内层循环结束时），程序会打印当前的数组状态以及本轮找到的最小值信息，帮助用户理解每一步的数据流向。

可观察结果：控制台输出如 implode(',',$list)."#pos=".($min + 1)." min=".$list[$min]."<br/>" 的内容。

第4步：判断并执行交换

内层循环完全结束后，检查记录的 $min 是否等于初始位置的 $i。如果不相等，说明找到了比当前位置更小的元素。

动作：使用临时变量进行三行赋值交换： $temp = $list[$i];
$list[$i] = $list[$min];
$list[$min] = $temp;
目的：将找到的最小值“选中”并放置到第 $i$ 个位置上，完成该位的定序。

第5步：循环收尾

外层的下一次迭代开始前，打印分隔线以示一轮排序的结束。重复直至所有位置都已完成固定。

代码实现详情

以下是完整的 PHP 实现代码，包含了详细注释与调试输出逻辑：

<?php
/**
 * 简单选择排序 simple selection sort
 *
 * 原理: 一次选定数组中的每一个数，记下当前位置并假设它是从当前位置开始后面数中的最小数min=i，
 * 从这个数的下一个数开始扫描直到最后一个数，并记录下最小数的位置min，扫描结束后如果min不等于i，
 * 说明假设错误，则交换min与i位置上数。
 */
function sort_simple_selection($list)
{
    $len = count($list);
    if(empty($len)) return $list;
    
    for($i = 0; $i < $len; $i++)
    {
        $min = $i; // 假设当前 i 位置是最小值的索引
        
        for($j = $i + 1; $j < $len; $j++)
        {
            // 寻找剩余未排序部分中的最小值
            // if($list[$j] > $list[$min]) // 如果是从大到小，则取消此处的注释并修改此处
            if($list[$j] < $list[$min]) // 从小到大排序逻辑
            {
                $min = $j; // 更新最小值索引
            }
            // 可选：输出内层扫描过程中的动态变化
            // echo implode(',',$list)."#pos=".($min + 1)." min=".$list[$min]."<br/>";
        }
        
        // 内层循环结束，如果找到的最小值不在当前位置 $i，则进行交换
        if($min != $i)
        {
            $temp = $list[$i];
            $list[$i] = $list[$min];
            $list[$min] = $temp;
        }
        
        echo "-------------------------<br/>";
        // 可选：输出本轮排序后的整体数组状态
        // echo implode(', ', $list) . "<br>";
    }
    return $list;
}

// 测试数据
$list = array(4, 3, 2, 1, 5, 7, 3, 7);
$result_list = sort_simple_selection($list);
?>

简要总结

简单选择排序通过不断的“选择”最小元素并进行“交换”，逐步完成数组排序。虽然效率不如快速排序等高级算法，但其逻辑简单、空间复杂度低（仅使用常数级额外空间），是理解排序算法思想的优秀入门案例。以上就是 PHP 简单选择排序算法实现的详细内容，更多关于 PHP 算法与数据结构优化的资料请关注本站其它相关文章！