0

我尝试使用添加的代码为列表实现合并排序。我遇到的问题，我不知道是什么原因造成的：如果我直接调用recursiveMergeSort，我会得到正确的排序列表，但是如果我尝试通过调用mergeSort对列表进行排序，我只会得到第一个列表元素。

IE 如果主要我有一个列表 = "d","a","f","g","b" 那么

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

我需要做什么才能让 mergSort 给出与 recursiveMergeSort 相同的结果？（公共 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;
}

（合并列表只是将两个有序列表合并为一个有序列表。）

4

1 回答 1

4

list是一个引用变量，引用一个 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);
}

您可以通过调用对象的方法或更改其中字段的值来更改对象，无论是对象本身还是对象的组件。 indexListin yourrecursiveMergeSort是起始列表中节点的另一个参考，您正在使用setNext(null)

于 2013-01-14T20:05:53.340 回答