原理

选择排序算是最自然的排序方式了，也是最直观的排序方式。第一轮从第一个数字开始一直遍历到最后一个数字，找到其中最小的数字放到最开始。下一轮则遍历剩余的数字，找到最小的也放到前面去，以此类推直到完成所有。

步骤

1. 第一轮从下标 0 的位置开始遍历直到最后一个，找到之中最小的数字挪到下标 0 的位置。
2. 接着从下标 1 的位置开始遍历到最后一个，找到之中最小的数字挪到下标 1 的位置。
3. 以此类推，直到只剩下最后一个数字。

此图来自：runoob.com 选择排序

代码

<?php declare(strict_types=1);

class Algorithm
{
    public function selectionSort(array $s): array{
        $e = count($s) - 1; // $e 末尾索引  
        for ($h = 0; $h < $e; $h++) { // $h 每一轮的起始索引   
            for ($i = $h+1; $i <= $e; $i++) {
                if ($s[$h] > $s[$i]) [$s[$h], $s[$i]] = [$s[$i], $s[$h]];
            }
        }
        return $s;
    }
}

时间复杂度

两层 n 次循环：O(n²)

最好情况（数组本身就是由小到大排序）：O(n²)

最坏情况（数组本身就是由大到小排序）：O(n²)

空间复杂度

循环中并无开辟并占据内存空间：O(1)