0

宿題があります - Java でマージ ソート アルゴリズムを書きます。LinkedList を使用してデータを保存しました。ウィキペディア ( http://en.wikipedia.org/wiki/Merge_sort )から擬似コードを Java に変換しようとしましたが、うまくいきません。理由がわからないので、皆さんの助けが必要です。

それは私の MergeSort クラスです。

import java.util.Comparator;

public class MergeSort {
private final Comparator comparator;

public MergeSort(Comparator comparator) {
    this.comparator = comparator;
}

public LinkedList sort(LinkedList list) {
    if(list.size() <= 1) {
        return list;
    }

    LinkedList left = new LinkedList();
    LinkedList right = new LinkedList();

    int middle = list.size() / 2;
    for(int i = 0; i < middle; i++) {
        left.add(list.get(i));
    }

    for(int i = list.size(); i >= middle; i--) {
        right.add(list.get(i));
    }

    left = sort(left);
    right = sort(right);

    return merge(left, right);
}

public LinkedList merge(LinkedList left, LinkedList right) {
    LinkedList result = new LinkedList();

    while(left.size() > 0 || right.size() > 0) {
        if(left.size() > 0 && right.size() > 0) {
            if(comparator.compare(left.get(0), right.get(0)) <= 0) {
                result.add(left.delete(0));
            }
            else {
                result.add(right.delete(0));
            }
        }
        else if(left.size() > 0) {
            result.add(left.delete(0));
        }
        else if(right.size() > 0) {
            result.add(right.delete(0));
        }
    }
    return result;
}

}

その中には「StackOverflowError Exception」があります。バグを取り除こうとしますが、できません。ご協力いただきありがとうございます。

PS私のひどい言葉で申し訳ありません。:(

4

1 に答える 1

0

33 行目で、上位配列インデックスはリスト サイズから 1 を引いた位置から開始する必要があります。

        for(int i = list.size()-1; i >= middle; i--) {
于 2013-04-24T18:07:40.857 に答える