归纳证明冒泡排序是 $O(n)$ 的。

对于冒泡排序第 $1$ 轮：显然是 $O(n)$ 的

如果前 $k$ 轮是 $O(n)$ 的：第 $k + 1$ 轮是 $O(n)$ 的，那么前 $k + 1$ 轮也是 $O(n)$ 的。

所以对于任意正整数 $k$，冒泡排序前 $k$ 轮是 $O(n)$ 的。

另一方面，如果对交换次数归纳，可以证明是 $O(1)$ 的！！！