二、选择排序
56 / 0 / 创建于 1年前 /
xiaer 的个人博客
原理
选择排序算是最自然的排序方式了，也是最直观的排序方式。第一轮从第一个数字开始一直遍历到最后一个数字，找到其中最小的数字放到最开始。下一轮则遍历剩余的数字，找到最小的也放到前面去，以此类推直到完成所有。
步骤
- 第一轮从下标 0 的位置开始遍历直到最后一个，找到之中最小的数字挪到下标 0 的位置。
- 接着从下标 1 的位置开始遍历到最后一个，找到之中最小的数字挪到下标 1 的位置。
- 以此类推，直到只剩下最后一个数字。
此图来自：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)
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号