php实现选择排序

PHP实现选择排序

选择排序是一种简单直观的排序算法，其基本思想是每次从未排序的部分选择最小（或最大）的元素，放到已排序部分的末尾。以下是PHP实现选择排序的代码示例：

function selectionSort($array) {
    $length = count($array);

    for ($i = 0; $i < $length - 1; $i++) {
        $minIndex = $i;

        for ($j = $i + 1; $j < $length; $j++) {
            if ($array[$j] < $array[$minIndex]) {
                $minIndex = $j;
            }
        }

        if ($minIndex != $i) {
            $temp = $array[$i];
            $array[$i] = $array[$minIndex];
            $array[$minIndex] = $temp;
        }
    }

    return $array;
}

代码说明

外层循环从数组的第一个元素开始，遍历到倒数第二个元素。内层循环从当前元素的下一个元素开始，遍历到数组末尾，寻找最小元素的索引。

找到最小元素后，如果最小元素的索引不等于当前元素的索引，则交换两个元素的位置。这样每次外层循环结束后，当前元素位置就会放置剩余未排序部分的最小值。

使用示例

$unsortedArray = [64, 25, 12, 22, 11];
$sortedArray = selectionSort($unsortedArray);
print_r($sortedArray);

输出结果：

Array
(
    [0] => 11
    [1] => 12
    [2] => 22
    [3] => 25
    [4] => 64
)

算法复杂度

选择排序的时间复杂度为O(n²)，其中n是数组的长度。这是因为对于每个元素，都需要遍历剩余的未排序部分来找到最小元素。空间复杂度为O(1)，因为排序是在原数组上进行的，只需要常数级的额外空间用于交换元素。