三、插入排序
0 / 0 / 创建于 2年前 /
xiaer 的个人博客
原理
插入排序模拟了我们打扑克牌的方式，从队列起始位置开始，逐一取出和之前已经排好顺序的数字比较，并在合适的位置将其插入。
步骤
- 第一轮从下标 1 的位置开始，和下标为 0 位置的数比较，如果比它小就插入到它前面。
- 接着把下标 2 位置数和 下标 0 以及 1 位置的数字比较，插入到合适的位置。
- 以此类推，直到最后一个数字。
此图来自：runoob.com 插入排序
代码
<?php declare(strict_types=1);
class Algorithm
{
public function insertionSort(array $s): array
{
$e = count($s) - 1;
for ($i = 1; $i <= $e; $i++) {
for ($j = $i; $j > 0; $j--) {
if ($s[$j] > $s[$j-1]) break;
[$s[$j], $s[$j-1]] = [$s[$j-1], $s[$j]];
}
}
return $s;
}
}时间复杂度
两层 n 次循环：O(n²)
最好情况（数组本身就是由小到大排序）：O(n)
最坏情况（数组本身就是由大到小排序）：O(n²)
空间复杂度
循环中并无开辟并占据内存空间：O(1)
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号