-1

我对 java 很陌生，我正在做一个需要使用合并排序的作业，但我继续遇到错误。我们正在使用 ArrayList，它导致我犯了很多错误。我发布了下面的代码以及我继续得到的错误，谁能帮我弄清楚为什么会这样？

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)
4

2 回答 2

1

这是因为您拥有的数组索引大于数组的大小减一。数组索引从 0 开始到 n-1

于 2013-05-09T02:20:41.160 回答
1

有几个问题。

  1. sortArray(0, list.size(), list);需要是sortArray(0, list.size() - 1, list);因为索引从 0 变为 size - 1；

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

  3. 合并所有末尾的下面的块需要更改，这样您就不会超出组合数组列表的 size() 范围。如下图所示。

前

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));
}
于 2013-05-09T02:38:35.417 回答