java - 合并排序 IllegalArgumentException

Question

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

我正在尝试按字母顺序对包含 5163 个名称的列表进行排序。我做了一些研究，发现 MergeSort 是一种相当有效的方法。

所以我根据这个 link 编写了一个实现.

下面是我的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 方法时，它会出现以下错误:

Exception in thread "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() 等于 0 的唯一方法。但是，我不明白为什么我的列表可能为零。因为要分到大小为一，然后再归还。

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

有人可以帮我指出我做错了什么吗？我确信这真的很简单，但由于我刚刚开始学习它，所以我不确定它是什么。

编辑:

我在这里检查列表的大小:

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

那么我的列表的大小怎么可能为零呢？

Answer 1

The only way I could see it equalling zero was if it was zero to begin with, but I have confirmed that my list.size() is 5163 to start with.

还有第二种方法。考虑在进入 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) .同样，由于结束索引是独占，这将创建一个长度为零的列表，或一个空列表。现在当你到达递归调用时

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----------------------------------^