1

我有一个类可以对通用列表进行一些递归合并排序，只要元素实现 Comparable。我有一个名为 mergeSort(List toSort) 的 void 方法和一个方法 mergeSortedLists(List left, List right)，它采用两个已经排序的列表，然后将它们组合成一个排序列表。问题是，mergeSort(...) 方法似乎没有操纵 toSort 变量。是的，但是在它跃升一个级别后不会显示更改。以下是排序方法：

public static <E extends Comparable<E>> void mergeSort(List<E> toSort)
{
  if(toSort.size() > 1)
  {
    List<E> temp = toSort.subList(0, toSort.size()/2);

    ArrayList<E> left = new ArrayList<E>(0);
      for(E e : temp) left.add(e);

    temp = toSort.subList(toSort.size()/2, toSort.size());

    ArrayList<E> right = new ArrayList<E>(0);
      for(E e : temp) right.add(e);

    if(right.size() != 1) mergeSort(right);
    if(left.size() != 1) mergeSort(left);

    toSort = mergeSortedLists(left, right);
  }
}


public static <E extends Comparable<E>> List<E> mergeSortedLists(List<E> leftList, List<E> rightList)
{
  ArrayList<E> list = new ArrayList<E>();

  while(!leftList.isEmpty() && !rightList.isEmpty())
  {
    if((leftList.get(0)).compareTo(rightList.get(0)) <= 0)
      list.add(leftList.remove(0));

    else
      list.add(rightList.remove(0));
  }

  while(!leftList.isEmpty())
    list.add(leftList.remove(0));

  while(!rightList.isEmpty())
    list.add(rightList.remove(0));

  return list;
}

我通常有用于错误检查的打印语句，这些语句表明 mergeSortedLists(...) 正确排序并返回正确的列表。然后，我将 mergeSort(...) 中的 toSort 变量分配给 mergeSortedLists(...) 返回的任何内容。该任务有效。现在，它跳回一个级别以将该列表与不同的列表组合在一起，并且更改似乎丢失了。我不知道发生了什么。

4

2 回答 2

1

参数（甚至是对对象的引用！）在 Java 中是按值传递的，因此您正在修改 的本地副本toSort，而不是调用函数中的副本。解决此问题的一种方法是返回您再次传入的列表，即

public static <E extends Comparable<E>> List<E> mergeSort(List<E> toSort)

然后你会说这样的话：

right = mergeSort(right);

等，并返回使用：

return mergeSortedLists(left, right);

我还没有通读其余的代码，但希望这能让你走上正确的道路:)

于 2012-04-26T23:32:38.827 回答
1

而不是这个

toSort = mergeSortedLists(left, right);

尝试

toSort.clear();
toSort.addAll(mergeSortedLists(left, right));

您的方法的问题是您重置了对列表的引用，但这不会传播回原始函数。建议的版本会操纵您被引用的原始列表。由于您不更改引用，因此对原始列表的更改将在函数返回后显示在调用者处。

澄清一下：当您将参数传递给函数时，会创建该参数的副本，该副本用作函数内的局部变量。当您更改该变量本身的值时，这些更改是对副本进行的，而不是对原始的（调用函数时复制的副本）。在建议的版本中，副本是一个引用，所以尽管引用被复制，但对象（这里：列表）不是，所以两个引用指向同一个对象。因此，通过副本（局部变量）对对象所做的更改会在函数返回时“显示”出来。

于 2012-04-26T23:36:11.500 回答