0 
public static void insertionSortRecursion(String a[], int first, int last) {
        if (first < last) {
            //sort all but last
            insertionSortRecursion(a, first, last - 1);
            insertInOrder(a[last], a, first, last -1);
        }
    }

    private static void insertInOrder(String element, String[] a, int first, int last) {
//        System.out.println(last - 1);
//        System.out.println(element);
//        System.out.println(a[last]);
        if (element.compareTo(a[last]) >= 0) {
            a[last + 1] = element;
        } else if(first < last) {
            a[last + 1] = a[last];
            insertInOrder(element, a, first, last - 1);
        } else {
            a[last + 1] = a[last];
            a[last] = element;
        }
    }

こんにちは、私は再帰を使用して挿入ソートを実装しようとしていますが、少数の単語では問題なく動作していますが、ソートしているファイルのサイズには約 10,000 の単語が多いため、実装後にスタックオーバーフローが発生します。エラーを取り除くために何をすべきかを提案してください。

These are the methods I am using for insertion sort using recursion and I am calling them in my constructor.
4

2 に答える 2

1

アルゴリズムが正しいと仮定すると、この関数はそのままにしておきます。直そうとしないでください。一般に、(再帰を維持しながら) スタック オーバーフローを取り除くには、2 つの解決策があります。

しかし、このコードはプログラミングの演習以外の何物でもないと仮定して考えてみましょう。読む必要がある他の人は次のように考えるでしょう：

  1. なぜ彼は挿入ソートを使用するのですか?
  2. なぜ彼は挿入ソートを再実装するのですか?
  3. 再帰でなければなりませんでしたか?? 閣下！！
  4. なぜ彼はテールコール挿入アルゴリズムを見つけるために時間を無駄にしたのでしょうか? または
  5. メソッドを実行するためだけにスタック サイズを増やしただけですか?
  6. 良い。1000,000ソートするアイテムがあり、プログラムがクラッシュし続けます。

結論として、彼らはあなたのコードをすぐに消去し、Collections.sort()を使用します。私が言ったように、プログラミングの練習をしているなら、再帰挿入ソートはある時点まで機能します。進め。

于 2013-02-05T09:04:09.957 に答える
0

Java は、デフォルトではその深さ (10000) の再帰の深さを処理できません。以下の非常に単純化された例でも StackOverflowError がスローされることを考慮してください。

static void test(int i)
{
   if (i == 0) return;
   test(i-1);
}

public static void main(String[] args)
{
   test(10000);
}

これを実現するには、コマンド ライン パラメーターを指定する必要があります (-Xss場合によって-Xmxは、より多くのメモリを割り当てる必要があります)。

を使用して、サイズ 100000 の配列に対してアルゴリズムを正常に実行しました-Xmx1000m -Xss10000000(時間がかかりましたが)。

単純な double for ループではなく、再帰を使用している理由があると思います。

于 2013-02-05T08:44:32.443 に答える