algorithm - 冒泡排序性能

Question

如果冒泡排序需要 200 秒来对 200 个名称进行排序，那么它可以在 800 秒内排序多少个项目？

计算比较次数可以为我们提供解决方案。我们如何计算对 200 个名称进行排序所需的比较次数？我们必须考虑最好的情况吗？

Answer 1

1. 冒泡排序是 O(n ² )。做你的数学。Big O 只是给出了一个相对时间的概念，你可以猜测大概的时间。不准确。
2. BubbleSort 第一次进行 n-1 次比较，第二次进行 n-2 次比较，以此类推。所以你有总(n-1) + (n-2) + .. +1。再做一些数学？
3. 冒泡排序太可悲了，没有最好的情况！^[1]

（显然你可以编写一个智能冒泡排序，它不对已经排序的数组进行排序）

BUBBLESORT A
 for i = 1 to A.length 1
  for j = A.length downto i+1
    if A[j]  < A[j - 1]
     exchange A[j] with A[j-1]

来自算法简介 - CLRS

---

[1] 在#3。请参阅http://en.wikipedia.org/wiki/Bubble_sort它提到了一个优化的内部循环，该循环识别了已排序的剩余数组并做出了最佳情况 O(n) - 对此感到抱歉。

Answer 2

800 是 4 x 200。冒泡排序是 O(n*n)，因此平均而言，您可以在 4 倍的时间内对两倍数量的项目进行排序，因此如果 200 是一个平均情况，那么平均预期是 400 个名称。