0

我写了下面的代码，但我得到了堆栈溢出。单独测试时，合并方法可以正常工作。当我现在查看代码时，我有隧道视野，我无法理解为什么它不起作用，所以有人可以向我指出错误。非常感谢！

public static List<Comparable> mergeSort(List <Comparable> target){
    if(target.size() <  2)
        return target;

    return merge(mergeSort(copy(0,(target.size()-1)/2 + 1,target)),mergeSort(copy((target.size()-1)/2 + 1,target.size(),target)));
}

private static List<Comparable> merge(List<Comparable> target1,List<Comparable> target2){
    List <Comparable> result = new ArrayList <Comparable>();

    while(target1.size() > 0 || target2.size() > 0){
        if(target1.isEmpty()) 
            result.add(target2.remove(0));
        else if(target2.isEmpty()) 
            result.add(target1.remove(0));
        else if(target1.get(0).compareTo(target2.get(0)) < 0)
            result.add(target1.remove(0));
        else    
            result.add(target2.remove(0));
    }

   return result;
}

private static List<Comparable> copy(int startIndex, int endIndex, List<Comparable> target){
    List <Comparable> result = new ArrayList <Comparable>();

    for(int i = startIndex; i < endIndex; i++)
       result.add(target.get(i)); 

    return result;
}
4

1 回答 1

1

我认为您的 mergeSort 实现不能很好地扩展。您正在使用您的copy方法将输入列表的适当范围复制为递归调用的输入mergeSort。如果您考虑递归的整个深度，则需要在每个级别上增加与整个输入列表大小相同的空间。

这意味着您的代码需要 log2(n) 乘以 n 的内存，其中 n 是输入列表的大小。如果您要对大小为 65'536 的元素列表进行合并排序，您的代码将创建它的副本，这样它将使用 log2(65'536) = 16 倍输入表内存需求的峰值。这很可能导致StackOverflowException.

为了解决这个问题，我将重写该mergeSort方法（或者更确切地说创建它的重载版本）以接受一个列表以及指向该列表的下限和上限。这样，您就不需要在每个递归步骤中复制列表。另一方面，只要由下限和上限分隔的范围仅包含一个元素，您就会返回一个List仅包含将对其进行操作的单个元素的新元素merge()。这样，您只需复制整个输入列表一次（即在最低递归级别），最终您将只使用输入列表占用的内存的两倍（在复杂性方面，O(n)）。一旦merge()通过了这些单元素列表并创建了一个新的中间结果列表，单元素列表将可用于 GC。

于 2013-04-28T13:09:58.020 回答