分析简单的冒泡排序循环（最坏情况）

Question

我得到了一个简单的伪代码算法：

for j=1 to A.length-1 //first line 
  for i =1 to A.length-j //second line 
    if A[i-1] >A[i]
      swap A[i-1] and A[i]

有人告诉我第二行是这样运行的（最坏情况：

n+(n-1)+...+2 = n(n+1)/2-1

我知道当第一行运行时，第二个循环运行 n 次，j 的每次下一次迭代，第二个循环少运行 1 次 (n-1) +(n-2) 等等。我明白这显然是一个总结，但我不明白为什么最后添加的是 2（对于第二行）。

如有任何意见，我们将不胜感激。

Answer 1

考虑到 A.length 是 n，您可以清楚地验证相同。我正在为你做这件事:

for j=1 to n-1 //first line 
  for i =1 to n-j //second line 
    if A[i-1] >A[i]
     swap A[i-1] and A[i]

因此，对于第 j = 1 处的外循环的第一次迭代，内循环运行s 从 1 到 n-1 次。 => n-1

外循环第二次迭代，内循环运行s从1到n-2次。 => n-2

第i次外循环，内循环运行1到n-i次，=> n-i .

外循环的最后一次迭代将在 j = n-1 时进行，内循环将运行 for i = 1 到 n-(n - 1) = 1 次。

所以，结果将是 n-1 + n-2 + ... + 1 = (n-1)*n/2.

SO，明明最后应该是1

I understand that it's clearly a summation, here but what I don't get is why the last thing added is 2 (FOR THE SECOND LINE).

我建议您与您的 friend/professor 讨论此事，显然，他错误地通知了您。这就是我在这里解决的问题。

人们普遍认为，当数组的前n-1个元素排序完毕后，最后一个元素就已经适合了。因此，他们通常会这样假设并离开最后一步。

但是，在计算 OR 算法中，我们（通常）计算这个。您的这段代码正在此处计算。

Analyzing Simple Bubble Sort Loop (Worst Case)