0

2 つのバブルソート アルゴリズムをコーディングしました。1 つは再帰なし、もう 1 つは再帰ありです。これら 2 つのどちらがより効率的で、その理由を説明することに興味があります。

再帰的バブルソート:

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;
}

ループを使ったBubbleSort:

 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;
}
4

2 に答える 2

3

どちらが優れているのかはわかりませんが、アルゴリズムの動作の性質上、バブルソートには本質的に最高のケースと最悪のケースのパフォーマンス時間が必要です。最良の場合 O(n) 最悪の場合 O(n^2) http://en.wikipedia.org/wiki/Bubble_sortを参照してください。反復と再帰はあまり大きな違いはありません。再帰はより多くのスタックメモリを消費すると思います。再帰は、反復よりも記述とトレースが難しい傾向があります。両方が実際のバブル ソートの実装である場合、時間のメリットがないため、反復に固執します。

于 2013-10-02T15:33:01.130 に答える
-1

上記の例では、ループを再帰に置き換えることが少なくなります。Java 再帰バージョンでは、長い配列の長さに基づいてスタックオーバーフロー エラーが発生する可能性があるため、おそらく適切ではありません。複雑さに関しては、違いはわかりません。JVMのメモリ管理を比較すると、再帰バージョンは通常のループよりも多くのメモリスペースを必要とします。変数の長さを増やすと、その違いに気付くか、メモリ世代に割り当てられたサイズに基づいてスタックオーバーフロー例外が発生する可能性があります。

于 2013-10-02T16:05:16.647 に答える