代码如下：
for (int i = 1; i < N; i++) {
if (a[i] < a[i-1]) {
swap(i, i-1);
i = 0;
}
}
在尝试了一些事情后，我认为最坏的情况是输入数组是降序 . 然后看起来比较将是最大的，因此我们将只考虑比较 . 然后它似乎是总和的总和，即...... {1 2 3 ...（n-1）} {1 2 3 ...（n-2）} {1 2 3 ...的总和... （n-3）} .... 1若是，那么O（n）是什么？
如果我不在正确的道路上，有人可以指出O（n）会是什么以及它是如何得出的？干杯！
3 回答
对于初学者来说，总结
实际上并不是O（n） . 相反，它是O（n3） . 你可以看到这个，因为总和1 2 ... n = O（n2，并且每个都有n个副本 . 通过查看前n / 2，你可以更正确地显示这个总和是Θ（n3）这些术语中的每一个都至少为1 2 3 ... n / 2 =Θ（n2），因此存在Θ（n2）的n / 2个副本，给出了Θ（n3）的紧束缚 .
我们可以在O（n3）处将该算法的总运行时间上限，注意每个交换将数组中的反转次数减少一个（反转是一对不对称的元素） . 数组中最多可以有O（n2）个反转，并且排序后的数组中没有反转（你明白为什么？），所以最多O（n2）遍历数组，每个最多需要O（ n）工作 . 这共同给出了O（n3）的界限 .
因此，您已识别的Θ（n3）最坏情况运行时渐近紧，因此算法在时间O（n3）中运行并具有最坏情况运行时间Θ（n3） .
希望这可以帮助！
它每次交换执行一次列表迭代 . 对于反转列表，必要的最大交换次数为
O(n * n). 每次迭代都是O(n).因此算法是
O(n * n * n).这是臭名昭着的泡泡排序的一半，其中有一个O（N ^ 2） . 这个局部排序有O（N），因为For循环从1变为N.在一次迭代之后，你将得到列表末尾的最大元素，并且列表的其余部分以某些变化的顺序结束 . 要成为一个合适的冒泡排序，它需要在这一个内部的另一个循环迭代j从1到N-i并做同样的事情 . If进入内循环 .
现在你有两个循环，一个在另一个里面，它们都从1到N（有点） . 您将进行N * N或N ^ 2次迭代 . 因此O（N ^ 2）用于冒泡排序 .
现在您已经作为程序员迈出了下一步：完成编写冒泡排序并使其正常工作 . 尝试使用不同长度的列表a并查看它需要多长时间 . 然后再也不用了 . ;-)