Bubblesort算法問題

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. 將這個算法終止？

   我有我的答案，因爲沒有becayse [i]和[j]永遠不會交換。

2. 作爲排序問題大小的函數，該算法在O-notation中的最壞情況時間複雜度是多少？

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。 SO不會做你的全部功課。