0

Java でマージ ソート クラスを作成していますが、その行に到達するとスタック オーバーフロー エラーが発生しますsort(left)。何かご意見は？なぜこれが問題になるのか理解できません。

パッケージ ds;

import java.util.Comparator;

public class MergeSorter<T> extends Sorter<T> {

public MergeSorter(Comparator<T> comparator){
    super(comparator);
}

@SuppressWarnings("unchecked")
@Override
public void sort(T[] array){
    if (array.length <= 1);
    else {
        T[] left = (T[]) new Object[array.length/2 + 1];
        T[] right = (T[]) new Object[array.length/2 + 1];
        int middleIndex = array.length / 2;
        for (int i = 0; i < middleIndex; i++) {
            left[i] = array[i];
        }
        for (int i = middleIndex; i < array.length; i++) {
            right[i - middleIndex] = array[i];
        }
        sort(left);
        sort (right);
        merge(left, right, array);
    }
}

public final void merge(T[] left, T[] right, T[] array){
    Array<T> sortedArray = new Array<T>(array.length);
    while (left.length > 0 || right.length > 0) {
        if (left.length > 0 && right.length > 0) {
            if (comparator.compare(left[0], right[0]) < 0) {
                sortedArray.add(left[0]);
                for (int i = 1; i < left.length; i++) {
                    left[i - 1] = left[i];
                    left[left.length - 1] = null;
                }
            }
            else {
                sortedArray.add(right[0]);
                for (int i = 1; i < right.length; i++) {
                    right[i - 1] = right[i];
                    right[right.length - 1] = null;
                }
            }
        }
        else if (left.length > 0) {
            sortedArray.add(left[0]);
            for (int i = 1; i < left.length; i++) {
                left[i - 1] = left[i];
                left[left.length - 1] = null;
            }
        }
        else if (right.length > 0) {
            sortedArray.add(right[0]);
            for (int i = 1; i < right.length; i++) {
                right[i - 1] = right[i];
                right[right.length - 1] = null;
            }
        }
    }
    for (int i = 0; i < array.length; i++) {
        array[i] = sortedArray.get(i);
    }
}

}
4

1 に答える 1

1

配列の長さがあるとし2ます。次に左は次のとおりです。

T[] left = (T[]) new Object[array.length/2 + 1];

これは

T[] left = (T[]) new Object[2/2 + 1];

そしてこれはに等しい

T[] left = (T[]) new Object[2];

そして、あなたがソートするとleft、これが続き、あなたが投稿したスタックオーバーフローエラーを引き起こした可能性のある無限再帰につながります.

middleIndex最初の要素を にコピーしているのでleft、middleIndex長さは配列にぴったり合うはずleftです。したがってleft、長さのarray.length/2配列にする必要があります。

于 2013-06-05T19:36:47.080 に答える