追加されたコードを使用して、リストのマージソートを実装しようとしました。私が遭遇した問題は、何が原因かわかりません。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つの順序付きリストを順序付きリストにマージするだけです。)