MergeSort IllegalArgumentException

Question

所以我现在正在学习MergeSort来解决Euler项目的一个问题。

我正在按字母顺序排列一个5163个名字的列表。我做了一些研究，发现MergeSort是一种非常有效的方法。

因此，我根据这个链接编写了一个实现。

下面是我的mergeSort和merge方法。

public static List<String> mergeSort(List<String> list){

    if (list.size() == 1){ //if fully divided
        return list;
    }

    List<String> leftSide = list.subList(0, list.size()/2);
    List<String> rightSide = list.subList(list.size()/2 + 1, list.size());

    leftSide = mergeSort(leftSide);
    rightSide = mergeSort(rightSide);

    return merge(leftSide, rightSide);

}

public static List<String> merge(List<String> listA, List<String> listB){

    List<String> listC = new LinkedList<String>();

    while (!listA.isEmpty() & !listB.isEmpty()){ //while both have elements
        if (listA.get(0).compareTo(listB.get(0)) > 1){ //if stringA is greater than stringB 
            listC.add(listA.get(0));
            listA.remove(0);
        } else { //if stringB is greater than stringA
            listC.add(listB.get(0));
            listB.remove(0);
        }
    }

    while (!listA.isEmpty()){ //while listA has elements 
        listC.add(listA.get(0));
        listA.remove(0);
    }

    while (!listB.isEmpty()){ //while listB has elements
        listC.add(listB.get(0));
        listB.remove(0);
    }

    return listC;

}

问题是，当我尝试在我的名字列表中使用mergeSort方法时，它会给出以下错误：

线程"main“java.lang.IllegalArgumentException中的异常: fromIndex(1) > toIndex(0)

它指向这一行：

List<String> rightSide = list.subList(list.size()/2 + 1, list.size());

我真的不明白为什么会发生这种事。在我看来，我使用了与本教程中所示的完全相同的方法。

而且，据我所知，这个错误告诉我，我的列表的大小是零。这将是list.size()/2 + 1可以等于1而list.size()可以等于零的唯一方法。但是，我不明白为什么我的名单可能是零。因为它将被除以，直到大小为1，然后它将被返回。

唯一能看到它等于零的方法是，如果它一开始是零，但我已经确认我的list.size()是5163开始。

有人能帮我指出我做错了什么吗？我确信这是一件很简单的事情，但由于我刚刚开始学习，我不知道它是什么。

编辑：

我在这里检查名单的大小：

System.out.println(namesArray.size()); //prints "5163"
namesArray = mergeSort(namesArray);

那么，我的名单怎么可能有一个零的大小呢？

Answer 1

唯一能看到它等于零的方法是，如果它一开始是零，但我已经确认我的list.size()是5163开始。

还有第二条路。考虑当输入到mergeSort时，输入子列表包含两个元素时，在递归中会发生什么。

List<String> leftSide = list.subList(0, list.size()/2);

上面的内容变成list.sublist(0,1)。因为结束索引是独占的，所以子列表包含一个元素。然后：

List<String> rightSide = list.subList(list.size()/2 + 1, list.size());

这就变成了list.sublist(2,2)。同样，由于结束索引是独占的，这将创建长度为零的列表，或者是emtpy列表。现在当您到达递归调用时

leftSide = mergeSort(leftSide);
rightSide = mergeSort(rightSide);

左侧递归工作，但右侧递归传递一个零长度列表。在mergeSort的顶端

if (list.size() == 1){ //if fully divided
    return list;
}

它检查列表大小为1的终止条件，但不阻止代码试图处理空的零长度列表。这就是导致您在此之后立即出现异常的原因。

如果将测试更改为if (list.size() <= 1)，则会防止异常，但仍然会出现问题，因为某些元素由于结束索引问题而无法排序。

正确的解决方案是更改一行：

List<String> rightSide = list.subList(list.size()/2 + 1, list.size());
                                                    ^^^
        Remove this----------------------------------^

Answer 2

如果你有一个空的列表，你打电话

List<String> rightSide = list.subList(0/2 + 1, 0);

所以你的from指数比toIndex大。这就产生了例外。

形成javadoc

返回此列表中指定的fromIndex (包括)和toIndex (独占)之间的部分的视图。(如果fromIndex和toIndex相等，则返回的列表为空。)返回的列表由此列表支持，因此返回列表中的非结构更改将反映在此列表中，反之亦然。返回的列表支持此列表支持的所有可选列表操作。此方法消除了显式范围操作(通常用于数组的类型)的需要。任何期望列表的操作都可以通过传递subList视图而不是整个列表作为范围操作。例如，以下成语从列表中移除一系列元素: list.subList( from，to).clear()； 可以为indexOf和lastIndexOf构造类似的成语，集合类中的所有算法都可以应用到subList中。如果支持列表(即此列表)在结构上被修改，而不是通过返回的列表，则此方法返回的列表的语义将变得不明确。(结构修改是那些改变列表大小的修改，或者以其他方式干扰它，以致正在进行的迭代可能产生不正确的结果。) 参数:来自索引- subList的低端点(包括) toIndex -子列表返回的高端点(独占)：此列表中指定范围的视图 抛出:IndexOutOfBoundsException--对于非法端点索引值(fromIndex <0欧元/( toIndex) > size \x- fromIndex > toIndex )。

你必须检查列表是否是空的。