java - Java中的归并排序

Question

我有一个类，只要元素实现 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(...) 返回的内容。该任务有效。现在，它跳回一个级别以将该列表与另一个列表合并，并且更改似乎丢失了。我不知道发生了什么。

Answer 1

而不是这个

toSort = mergeSortedLists(left, right); 

尝试

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

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

澄清一下:当您将参数传递给函数时，会创建该参数的副本，该副本充当函数内的局部变量。当您更改该变量本身的值时，这些更改将对副本进行，而不是对原始变量(调用函数时从中创建副本)进行。在建议的版本中，副本是引用，因此尽管引用被复制，但对象(此处:列表)却没有被复制，因此两个重新引用指向同一个对象。因此，通过副本(局部变量)对对象进行的更改会在函数返回时“显示”。