在Java中合并排序

我有一个类在通用List上做了一些递归合并排序，只要元素实现了Comparable即可。我有一个名为mergeSort（List toSort）的void方法和一个方法mergeSortedLists（List left，List right），它接受两个已经排序的列表，然后将它们组合成一个排序列表。问题是，mergeSort（...）方法似乎没有在操作toSort变量。好吧，但是这些变化并没有在跳出一个关卡后出现。以下是排序方法：在Java中合并排序

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（...）返回的值。该作业适用。现在，它跳回到一个级别，将该列表与不同的列表结合起来，并且这些更改似乎丢失了。我不知道发生了什么。

来源

2012-04-26 mottese

取而代之的是

toSort = mergeSortedLists(left, right);

尝试

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

的问题，你的做法是，你重置参考名单，但不会传播回原来的功能。建议的版本操纵您引用的原始列表。由于您不更改引用，因此函数返回后，原始列表的更改将显示在调用方处。

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

来源

2012-04-26 23:36:11 Attila

@ user1359900：出于我在我的回答（和Attila指出）中提到的原因 - Java中的参数传递始终是值，而不是引用。这里有一个看起来很合理的链接（请忽略标题，虽然我没有用尖锐的方式发布它）：http://javadude.com/articles/passbyvalue.htm – 2012-04-26 23:41:49

重要的一点是，假设参数传递是按照Java的价值，你需要找到一种方法来修改原始列表。 Attila的方法是通过传入的引用来处理原始列表，而不是尝试创建新列表;我给出的方法是创建一个新列表，但将其返回，以便可以将其分配到原始列表中。两者都会在这种情况下工作。（如果你使用不可变列表工作，那么情况就不是这样 - 在这种情况下，你必须采用返回方法。）我想Attila的方法更加紧迫，我的功能更强大。 – 2012-04-26 23:44:26

@ user1359900 - 查看我更新的答案 – Attila 2012-04-26 23:46:41

参数（即使引用对象！）在值以Java传递，因此您要修改本地副本toSort，而不是调用函数中的那个。解决此获得的一个办法是回到您再次通过列表，即

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

然后你会说这样的话：

right = mergeSort(right);

等，并返回使用：

return mergeSortedLists(left, right);

我还没有彻底地通读其余的代码，但希望这应该让你在正确的线:)

来源

2012-04-26 23:32:38

在Java中合并排序

回答

相关问题