一、冒泡排序

原理

每次只移动一位，一轮循环后，将最大的数移动到队列的末尾。然后剩余的数以此类推，直到剩余的数只有 1 个。整个流程就像气泡在水中往上冒一样，所以叫冒泡排序。

步骤

1. 第一轮冒泡，从下标 0 和 1 的位置开始比较，若下标 0 的数比下标 1 的数大，则交换位置，否则保持不变。
2. 接着比较下标 2 和 3，以此列推直到下标 n-1 和 n 做比较，至此完成一轮。
3. 然后是第二轮，这一轮依然是从下标 0 和 1 开始，但结尾变成了 n-2 和 n-1的比较，因为经过上一轮的比较，下标 n 的位置已经是所有数中最大的了。
4. 依次往复，直到最后可比较的下标只剩下 0 为止。

此图来自：runoob.com 冒泡排序

代码

<?php declare(strict_types=1);

class Algorithm
{
    public function bubbleSort(array $s): array
    {
        $e = count($s) - 1; // 最后一个数的索引
        while ($e > 0) {
            for ($i = 0; $i < $e; $i++) {
                if ($s[$i] > $s[$i+1]) [$s[$i], $s[$i+1]] = [$s[$i+1], $s[$i]];
            }
            $e--; // 将最后索引逐渐提前，缩小冒泡范围
        }
        return $s;
    }
}

时间复杂度

关于时间复杂度的几个概念以及约定：

1. 程序执行时间在不同编译器编译下，以及不同硬件环境下都是不同的，因此并不能通过公式计算出准确时间，但我们可以通过假定单条语句执行时间为固定值，通过计算语句执行次数来预估执行时间的多少。
2. 当程序中只有顺序执行，没有循环递归等结构时，时间是一个常数值，记为 O(1)。
3. 当程序中出现循环等结构时，程序的执行时间与循环边界 n 构成一个多项式函数 f(n)，如：f(n) = 3n²+6logn+7n+5，这里的 n 被称为特征值。
4. 在表达程序时间复杂度时，为了简便通常采用 渐进记法，即：取多项式中的最大项，并将其系数变为 1，以此作为这段程序的时间复杂度，所以 3n²+6logn+7n+5 的时间复杂度为：O(n²)。
5. 常见的项大小：1 < logn < n < nlogn < n² < n³ < 2ⁿ < n!

冒泡排序的时间复杂度计算：

n-1 + n-2 + n-3 + ... + [n-(n-1)]
= { n-1 + n-2 + n-3 + ... + [n-(n-1)]   +   [n-(n-1)] + ... + n-3 + n-2 + n-1  } ÷ 2
= (n + n + n + ... + n) ÷ 2
= n x (n-1) ÷ 2
= ½n²-½n
≈ O(n²)

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

空间复杂度

关于空间复杂度的几个概念以及约定：

1. 和时间复杂度类似，空间复杂度也只是对程序所使用内存空间的估计。
2. 当程序中只有顺序执行，没有循环递归等结构时，所使用的内存空间是一个常数值，记为 O(1)。
3. 当程序中出现循环等结构时，程序运行所需内存空间与循环边界 n 构成一个多项式函数 f(n)，如：f(n) = 3n+1，这里的 n 被称为特征值。
4. 类似时间复杂度，这里也采用同样的 渐进记法，所以多项式 3n+1 的空间复杂度记为：O(n)。

很多时候虽然有多层循环，但是每层循环中都没有开辟并持续占据内存空间，所以时间复杂度仍然是 O(1)，也就是说内存空间并不随循环边界 n 的变化而变化，这里的冒泡排序就是如此，因此空间复杂度为 O(1)。

本作品采用《CC 协议》，转载必须注明作者和本文链接