遞歸BubbleSort vs正常BubbleSort

我已經編碼了2個bubblesort算法。一個是沒有遞歸，另一個是遞歸。我有興趣瞭解這兩種方法哪一種效率更高，並解釋原因。遞歸BubbleSort vs正常BubbleSort

遞歸冒泡：

private static int list[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; 

public int[] recursiveBubble(int[] args, int startIndex, int endIndex) { 
    if(startIndex > endIndex){ 
     System.out.println("Recursive bubblesort:"); 
     System.out.println(Arrays.toString(args)); 
     return args; 
    } 

    if (startIndex == endIndex - 1) { 
     recursiveBubble(args, 0, endIndex - 1); 
    } else if (args[startIndex] > args[startIndex+1]) { 
     int currentNumber = args[startIndex]; 
     args[startIndex] = args[startIndex + 1]; 
     args[startIndex + 1] = currentNumber; 

     recursiveBubble(args, startIndex + 1, endIndex); 
    } else { 
     recursiveBubble(args, startIndex + 1, endIndex); 
    } 
    return args; 
}

使用冒泡循環：

public int[] bubblesort(int[] args) { 
    System.out.println("Normal BubbleSort:"); 
    for (int j = 0; j < args.length; j++) { 
     for (int i = 0; i < args.length; i++) { 
      int currentNumber = args[i]; 
      if (i + 1 < args.length) { 
       if (currentNumber > args[i + 1]) { 
        args[i] = args[i + 1]; 
        args[i + 1] = currentNumber; 
       } 
      } 
     } 
    } 
    System.out.println(Arrays.toString(args)); 
    return args; 
}

來源

2013-10-02 JP24

可能的重複：http://stackoverflow.com/questions/72209/recursion-or-iteration –

這不是論壇這樣的問題 - 嘗試[代碼評論]（http://codereview.stackexchange.com /）。 –

@SimonArsenault值得注意的是，javac不會執行尾遞歸優化，並且上述方法在任何情況下都不是尾遞歸。 –

我不知道你的意思由哪個更好，但冒泡排序必須本身有一個最佳和最差情況下的性能時算法工作方式的本質。最佳情況O（n）最壞情況O（n^2）見http://en.wikipedia.org/wiki/Bubble_sort。迭代與遞歸不應該有太大的區別。我想遞歸會佔用更多的堆棧內存。遞歸往往比迭代更難以書寫和追蹤。既然沒有時間利益，如果兩者都是實際的氣泡排序實現，我會堅持迭代。

來源

2013-10-02 15:33:01

好吧，基本上我的意思是哪一個跑得最快。由於我無法在netbeans上找到運行時。它只會說0秒。所以我只想知道哪一個能在運行時間內達到最快的目標。 – JP24

雖然你說得對，算法的最佳情況和最壞情況的性能往往不會改變。 – JP24

如果你已經正確編碼，差異_should_可以忽略不計。嘗試在龐大的數據集和分析上運行它，但我會驚訝地發現有很大的差異。這是功課嗎？ http://stackoverflow.com/questions/895371/bubble-sort-homework?rq=1 –

-1

在上面的例子中，你更少用循環代替遞歸。在java遞歸版本可能不好，因爲它可能導致基於長數組長度的計算器錯誤。複雜性明智我沒有看到任何區別。如果您比較JVM的內存管理，那麼遞歸版本將比正常循環更耗費內存空間。如果你增加變量的長度，你可能會注意到這種差異，或者你可能會遇到一個基於你的內存世代的分配大小的stackoverflow異常。

來源

2013-10-02 16:05:16

遞歸BubbleSort vs正常BubbleSort

回答

相關問題