algorithm - 冒泡排序算法题

Question

我有一个很困惑的问题，已经研究了一段时间，但似乎找不到任何帮助。

input a: array [1 .. n] of integer; n : integer;
temp  i, j : integer;
j <-- n;
while j ≥ 1
    do   I <-- 1;
        while   i ˂ j
            do
                if  a[i] ˃ a[j]  then swap a[i], a[j];
                i <-- i + 1;
            od;
        j < j – 1;
    od  

1. 这个算法会终止吗？

   我的答案是不，因为 a[i] 和 a[j] 永远不会交换。

2. 此算法的最坏情况时间复杂度(以 O 表示法作为排序问题大小的函数)是多少？

3. 该算法的前提条件是真值TRUE。该算法所需的后置条件是:for i ˂ j, a[i] ˂ a[j], for i = 1, 2, . . . , n-1, j = 2, . . . , n

找到您认为在算法终止时会导致所需后置条件的内循环和外循环的两个循环不变量。

任何帮助将不胜感激!我想明白这一点!

Answer 1

我建议您先阅读以下内容:http://en.wikipedia.org/wiki/Bubble_sort

关于你的问题。

1) 是的，算法肯定会终止。它将执行双循环并完成。

2) 最差的复杂度是 O(n^2)。

3)研究并记下:http://en.wikipedia.org/wiki/Loop_invariant .所以不会做你的全部作业。