Java归并排序收到错误信息

Question

我是java的新手，我正在做一个分配，我们需要使用归并排序，但我继续得到错误。我们用的是数组列表它让我犯了很多错误。我张贴了下面的代码以及我继续得到的错误，谁能帮我弄清楚为什么会发生这种情况?

import java.util.ArrayList;
import java.util.UUID;
public class mSort {
public static ArrayList<String> randomList() {
    ArrayList<String> a = new ArrayList<String>();
    for(int i = 0; i < 10; i++) {
        a.add(i, UUID.randomUUID().toString());
    }
    return a;
}
public void sort(ArrayList<String> list) {
    sortArray(0, list.size(), list);
}
private void sortArray(int low, int high, ArrayList<String> list) {
    if ((high - low) >= 1) {
        int middle1 = ( low + high ) / 2;
        int middle2 = middle1 + 1;
        sortArray(low, middle1, list);
        sortArray(middle2, high, list);
        merge(low, middle1, middle2, high, list);
    }
}
private void merge(int left, int middle1, int middle2, int right, ArrayList<String> list) {
    int leftIndex = left;
    int rightIndex = middle2;
    int combinedIndex = left;
    ArrayList<String> combined = new ArrayList<String>();
    ArrayList<String> data = list;
    while (leftIndex <= middle1 && rightIndex <= right) {
        if (data.get(leftIndex).compareTo(data.get(rightIndex)) < 0) {
            combined.add(combinedIndex, data.get(leftIndex));
            combinedIndex++;
            leftIndex++;
        }
        else {
            combined.add(combinedIndex, data.get(rightIndex));
            combinedIndex++;
            rightIndex++;
        }
    }
   if (leftIndex == middle2) {
       while (rightIndex <= right) {
           combined.add(combinedIndex, data.get(rightIndex));
           combinedIndex++;
           rightIndex++;
       }
   }
   else {
       while ( leftIndex <= middle1 ) {
           combined.add(combinedIndex, data.get(leftIndex));
           combinedIndex++;
           leftIndex++;
       }
   }
   for (int i = left; i <= right; i++ ) {
       list.set(i, combined.get(i));
       //System.out.println(list.get(i));
   }
}
public static void main(String[] args) {
    ArrayList<String> list = randomList();
    mSort sorted = new mSort();
    sorted.sort(list);
    for ( int i = 0; i < list.size(); i++ ) {
        System.out.println(list.get(i));
    }
}

}

下面是错误的堆栈跟踪:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 3, Size: 0
at java.util.ArrayList.rangeCheckForAdd(Unknown Source)
at java.util.ArrayList.add(Unknown Source)
at mSort.merge(mSort.java:40)
at mSort.sortArray(mSort.java:27)
at mSort.sortArray(mSort.java:25)
at mSort.sortArray(mSort.java:26)
at mSort.sortArray(mSort.java:25)
at mSort.sort(mSort.java:17)
at mSort.main(mSort.java:74)

Answer 1

有几个问题。

1. sortArray(0, list.size(), list);需要为sortArray(0, list.size() - 1, list);，因为索引从0到大小为- 1;

2. 合并combined.add(combinedIndex, data.get(rightIndex));行
   您不能向超出此范围的索引添加0 <= index <= size。当你这样做，它应该抛出一个IndexOutOfBoundsException根据文档。(确实如此)。这就是您看到异常的原因。组合数组列表的大小是0，你试图在索引3处插入。
   您可以将所有这些行更改为仅combined.add(data.get(...));(删除combinedIndex)。不应该需要combinedIndex变量，因为数组应该已经部分排序，所以追加应该保持它的排序。

3. 下面的块在合并所有的结束需要改变，所以你不会得到的大小()以外的组合数组列表。所示。

之前

for (int i = left; i <= right; i++ ) {
    list.set(i, combined.get(i));
}

后

for (int i = left; i <= right; i++ ) {
    list.set(i, combined.get(i - left));
}

Answer 2

由于数组索引大于数组的大小减1，所以会发生这种情况。数组索引从0开始到n-1