0

私のコードでは、メソッドはそれ自体を呼び出します (再帰)。深いメソッド呼び出しがスタック オーバーフローにつながることはわかっています。では、大量のデータがある場合、スタック オーバーフローは発生しますか?

私のQuickSortコード：（ソートクラスの内部クラス）

private static class QuickSortor extends Sortor {

    protected <E> void sort(E[] a, boolean isAsc) {
        quickSort(a, 0, a.length - 1, isAsc);
    }

    private <E> void quickSort(E[] a, int left, int right, boolean isAsc) {
        if (left >= right)
            return;
        int middle = left;
        Comparable<E> cmp = (Comparable<E>) a[left];
        for (int i = left + 1; i <= right; i++) {
            int result = cmp.compareTo(a[i]);
            if (!isAsc)
                result = -result;
            if (result >= 0)
                swap(a, ++middle, i);
        }
        swap(a, left, middle);
        quickSort(a, left, middle - 1, isAsc);
        quickSort(a, middle + 1, right, isAsc);
    }
}
4

2 に答える 2

5

再帰の深さとクイックソートにかかる時間は、データ ポイントの相対的な順序とその数によって異なります。ピボット ポイントが常にデータの最大または最小のメンバーになる場合、上記のコードを再帰すると、データ サイズと同じくらい深く再帰します。

クイックソートを使用すると、時間がかかる場合でも、再帰の深さを小さくすることができます。これについては、次のようにhttp://en.wikipedia.org/wiki/Quicksortで非常に簡単に説明されています。

最大で O(log N) のスペースが使用されるようにするには、最初に配列の小さい方の半分に再帰し、末尾呼び出しを使用してもう一方に再帰します。

非常に簡単に言えば、これはまず最初に書き直すことを意味します

f(...)
{
  ...
  f()
  f()
}

なので

f()
{
  while (...)
  {
    ...
    f()
    ...
 }
}

(while ループを使用して f の引数を変更し、2 番目の再帰呼び出しが while ループの 2 番目のパスに対応するようにします)。

次に、2 つの再帰呼び出しの配列をどのように分割したかを確認し、2 番目の再帰呼び出し (while ループに変換される) が配列の大きい方の半分であることを確認します。これは、残りの再帰呼び出しが常に配列の半分以下であることを意味します。つまり、配列サイズの底 2 の対数よりも深くなることはありません。

于 2012-06-20T04:00:45.720 に答える
2

書かれているアルゴリズムは、常に左端の要素をピボットとして選択します。すでにソートされている配列に対して実行するとO(n^2)、QuickSort の異常な動作が発生し、非常に小さな配列でスタック オーバーフローが発生します。

Integers0 から 15000 までの数字の配列に対して順番に並べ替えを呼び出すことで、それを試すことができます。私はそれをStackOverflowError試してみます。15000 個の randomIntegerの配列に対して実行しても、スタック オーバーフローは発生しません。

于 2012-06-20T04:12:25.433 に答える