0

追加されたコードを使用して、リストのマージソートを実装しようとしました。私が遭遇した問題は、何が原因かわかりません。recursiveMergeSortを直接呼び出すと、正しい並べ替えられたリストが返されますが、mergeSortを呼び出してリストを並べ替えようとすると、最初のリストしか取得されません。エレメント。

IEメインにリストがある場合="d"、 "a"、 "f"、 "g"、 "b" then

list = recursiveMergeSort(list) // list will be "a","b","d","f","g"
mergeSort(list) // list will be "a"

recursiveMergeSortと同じ結果を得るには、mergSortに対して何をする必要がありますか?(パブリックvoid関数はAPIで私に与えられたので、私はプライベート再帰関数を作成しました)

public static void mergeSort(List list) {
if (list == null) throw new NullPointerException("list");
    list = recursiveMergeSort(list);
    /* If I check list here, I get the correct result,
    only in the original it's wrong */
}
/** a recursive function for the merge sort  */
private static List recursiveMergeSort(List list) {

    int length = listLength(list);
    System.out.println(length);
    if (length <= 1) { // base case, list length 1
        return list;
    }

    // create sublists
    List left = new List(), right = new List();
    List.Node indexList = list.head;
    left.head = list.head;
    for (int i = 0; i < length / 2 - 1; i++ ) {
        indexList = indexList.getNext();
    }
    right.head = indexList.getNext();
    indexList.setNext(null);

    left = recursiveMergeSort(left); // recursively work on them
    right = recursiveMergeSort(right);
    List tempList = mergeLists(left, right); // final result
    return tempList;
}

(マージリストは、2つの順序付きリストを順序付きリストにマージするだけです。)

4

1 に答える 1

4

listリスト値を参照する参照変数です。

参照する変数の値を変更するだけでは、参照する値を変更することはできません。

初期関数を次のように変更します。

public static List mergeSort(List list) {
if (list == null) throw new NullPointerException("list");
    return recursiveMergeSort(list);
}

返される値は、ソートされたリストになります。

引数を変更する必要がある場合は、次のことを試してください。

public static void mergeSort(List list) {
if (list == null) throw new NullPointerException("list");
    List temp = recursiveMergeSort(list);
    list.clear();
    list.addAll(temp);
}

オブジェクトのメソッドを呼び出すか、オブジェクト自体またはオブジェクトのコンポーネントのいずれかでオブジェクト内のフィールドの値を変更することにより、オブジェクトを変更できます。 indexListあなたのrecursiveMergeSort中にはあなたのスターティングリストのノードの別の参照があり、あなたはそれをで変更していますsetNext(null)

于 2013-01-14T20:05:53.340 に答える