這是一個正確的BubbleSort算法嗎？

我寫了下面的代碼來使用BubbleSort對數組值中的元素進行排序。這是正確的還是有什麼缺失？我的測試用例很好，但也許測試用例也缺少一些東西。這是一個正確的BubbleSort算法嗎？

public void sort(ValuePair[] values) { 

    ValuePair value = null; 

    for (int i = 0; i < values.length; i++) { 
     for (int j = 1 + i; j < values.length; j++) { 
      if (values[i].getValue() > values[j].getValue()) { 
       value = values[j]; 
       values[j] = values[i]; 
       values[i] = value; 
      } 
     } 
    } 
}

來源

2014-01-20 Fischer Ludrian

我想你應該把這個帖子轉移到https://codereview.stackexchange.com/ –

那麼，如果你的測試案例工作，那麼你爲什麼認爲這是不正確的？請參閱此鏈接（http://www.sorting-algorithms.com/bubble-sort） – OldProgrammer

values.length -1？ – user2837260

您的代碼是正確的，它會對數組進行排序。但是它總是需要N *（N-1）次通過陣列。這不是用於實現泡沫排序的典型算法。典型的算法使用重複循環和排序的測試。這樣更有效，因爲一旦數組排序就終止（考慮你從一個有序數組開始的情況）。

閱讀Wikepedia article on bubble sort它證明了這一點。

冒泡排序的有些改進版的僞版本是這樣的：

procedure bubbleSort(A : list of sortable items) 
    n = length(A) 
    repeat 
     swapped = false 
     for i = 1 to n-1 inclusive do 
      if A[i-1] > A[i] then 
      swap(A[i-1], A[i]) 
      swapped = true 
      end if 
     end for 
     n = n - 1 
    until not swapped 
end procedure

這裏的教訓是，儘管你的算法和Wikepedia算法都具有相同大O特性，一個小的變化在他們實施的方式可以使他們的實際表現特徵發生重大變化。

來源

2014-01-20 15:53:44 NealB

這是一個正確的BubbleSort算法嗎？

回答

相關問題