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) —— 对此感到抱歉。