java - 无法弄清楚我的通用 mergeSort、IndexOutBoundException 错误

Question

这就是我到目前为止所拥有的......

public class SortUtil {
// Add any instance variables here //
SortUtilComparator comparatorObj = new SortUtilComparator();

public SortUtil() {
}

/**
 * This method performs a mergesort on the generic ArrayList given as input.
 * 
 * @param arrayMerge - the generic ArrayList to sort
 * @param comparator - comparator to compare the elements
 */
public static <T> void mergesort(ArrayList<T> arrayMerge, Comparator<? super T> comparator) {
    ArrayList<T> tempArray = new ArrayList<T>();
    mergesortRecursive(arrayMerge, tempArray, 0, arrayMerge.size()-1, comparator);
}

/**
 * 
 * @param arrayMerge -  ArrayList to sort
 * @param tempArrayList - temporary ArrayList used to merge
 * @param left - the first index of the range to sort
 * @param right - last index of the array range to sort
 * @param comparator - comparator to compare the elements
 */
public static <T> void  mergesortRecursive(ArrayList<T> arrayMerge, ArrayList<T> tempArrayList, int left, int right, Comparator<? super T> comparator ) {
    if (left == right){
        return;
    }

    if(left < right && (right-left) >= 1){
        int mid = (left + right) / 2;

        mergesortRecursive(arrayMerge, tempArrayList, left, mid, comparator); 
        mergesortRecursive(arrayMerge, tempArrayList, mid+1, right, comparator);

        // Sorts the first and second half of the ArrayList
        merge(arrayMerge, tempArrayList, left, mid, right, comparator); // and merges/sorts the array in the merge() method
    }
}

/**
 * Sorts the ArrayList using merge sort algorithm.
 * 
 * @param arrayValues - the ArrayList needing to be sorted / merged
 * @param tempArray - temporary ArrayList used for merging
 * @param start - the first index of the range to sort
 * @param mid - the first index of the range to sort
 * @param end - last index of the array range to sort
 * @param comparator - comparator to compare the elements
 */
public static <T> void merge(ArrayList<T> arrayValues, ArrayList<T> tempArrayList, int start, int mid, int end, Comparator<? super T> comparator ){

    // Next element to consider in the first half of arrayValues<T>
    int startValueIndex = start; 

    // Next element to consider in the second half of arrayValues<T>
    int midValueIndex = mid + 1;

    // As long as neither start or mid pass the end, move the smaller element into tempArrayValues<T>
    while(startValueIndex <= mid && midValueIndex <= end)
    {

        if(comparator.compare(arrayValues.get(startValueIndex), arrayValues.get(midValueIndex)) <= 0){
            tempArrayList.add(arrayValues.get(startValueIndex)); // adds smaller element of the left array on farthest left index into temporary array
            startValueIndex++; // increments this index so it can check
        }
        else{
            tempArrayList.add(arrayValues.get(midValueIndex)); // adds smaller element of the right array on farthest left index into temporary array
            midValueIndex++;
        }
    }

    // Only one of the while loops below will execute if there's still remaining elements.

    // Take remaining elements of the first half ArrayList
    while(startValueIndex <= mid){
        tempArrayList.add(arrayValues.get(startValueIndex));
        startValueIndex++;
    }

    // Take remaining elements of the second half ArrayList
    while(midValueIndex <= end){
        tempArrayList.add(arrayValues.get(midValueIndex));
        midValueIndex++;
    }

    int i = 0;
    int j = start;
    while(i < tempArrayList.size()){
        arrayValues.set(j, tempArrayList.get(i++));
        j++;
    }
}

我得到的错误是:

java.lang.IndexOutOfBoundsException: Index: 5, Size: 5
at java.util.ArrayList.rangeCheck(ArrayList.java:653)
at java.util.ArrayList.set(ArrayList.java:444)
at assignment05.SortUtil.merge(SortUtil.java:149)
at assignment05.SortUtil.mergesortRecursive(SortUtil.java:94)
at assignment05.SortUtil.mergesortRecursive(SortUtil.java:90)
at assignment05.SortUtil.mergesortRecursive(SortUtil.java:91)
at assignment05.SortUtil.mergesort(SortUtil.java:71)
at assignment05.SortUtilTests.mergeSort_Test1(SortUtilTests.java:49)

我一直在试图弄清楚它，稍微改变一下代码的排序方式，但我就是不知道它是如何得到异常的。我已经进行了调试并做了一些系统输出打印测试，但是，我只是不知道此时我可以做什么来让它工作。

编辑:这就是我尝试测试它的方式:

@Test
public void mergeSort_Test1() {
    ArrayList<Integer> values = new ArrayList<Integer>();
    values.add(1);
    values.add(5);
    values.add(7);
    values.add(2);
    values.add(10);

    ArrayList<Integer> expectedValuesArrayList = new ArrayList<Integer>();
    expectedValuesArrayList.add(1);
    expectedValuesArrayList.add(2);
    expectedValuesArrayList.add(5);
    expectedValuesArrayList.add(7);
    expectedValuesArrayList.add(10);

    SortUtil.mergesort(values, comparatorObj);
    Assert.assertEquals(expectedValuesArrayList, values);
}

我的 SortUtilComparator 是:

public class SortUtilComparator implements Comparator<Integer> {

public int compare(Integer o1, Integer o2) {
    return o1.compareTo(o2);
}

Answer 1

您正在向您添加越来越多的元素ArrayList<T> tempArrayList每次调用 merge功能。因此，您终于来到了您的 tempArrayList 的时刻。比你的原始数组大，所以当分配 tempArrayList 时到原始数组arrayValues.set(j, tempArrayList.get(i++));你得到IndexOutOfBoundsException .

您必须在每次调用 merge 时使用新的临时数组或在开头使用 tempArrayList.clear() 清除它.