<分区>
关于冒泡排序时间复杂度的问题还有其他问题，但这个问题不同。每个人都说冒泡排序的最坏情况是 O(n^2)。在列表的 i 次迭代后的冒泡排序中，列表的最后 i 个元素是有序的，不需要再次触摸或比较。如果您不必要地一次又一次地遍历最终元素，则时间复杂度仅为 O(n^2)。
鉴于冒泡排序的一个主要特点是(输入大小减去迭代)之后的元素永远不需要再次比较，因为它在正确的位置，为什么说冒泡排序时间复杂度是对我来说我不认为是冒泡排序？即使在维基百科中，它也说时间复杂度是 O(n^2)，然后在文章的中途它提到它可以“优化”到只需要大约 50% 的时间，而不是不必要地比较最后一个 i 元素。
我想起了这一点，因为我正在制作一个循环来检查我在世界上所有对象的碰撞，我检查的模式是:
for (int i = 0; i < numberofobjects - 1; i++)
{
{
for (int iplusone = i + 1; iplusone < numberofobjects; iplusone++)
// check collision between i and iplusone
}
}
对于 400 个对象，O(n^2) 的时间复杂度为 400 * 400 = 160,000。然而它只做了 79,800 次比较，大约 50%，这正是维基百科所说的。这让我想起了冒泡排序，所以当我检查时，我很惊讶地看到每个人都说它是 O(n^2)。
这是否意味着每当有人提到冒泡排序时，他们指的是不必要地重复已排序的最终元素的版本？此外，当比较不同的算法时，冒泡排序总是表现更差，但作者指的是明显糟糕的 n^2 版本吗？