递归合并排序出界异常排序

我想知道是否有人可以帮我找出为什么我在这段代码中出现了一个Out of Bounds异常。我已经尝试了一切。 Eclipse说它发生在mergeSortRecursive和merge调用。谢谢！递归合并排序出界异常排序

//封装方法

public static <E extends Comparable <E>> void mergeSort (E[]list){ 
    mergeSortRecursive(list, 0, list.length-1); 
}

//归并递归，取入左指针和右侧指针，其包装类表示为0和list.length -1

private static <E extends Comparable<E>> void mergeSortRecursive(E[] list, int left, 
     int right) { 
    // Base case 
    if (left == right) { 
     return; 
    } 
    int mid = left + right/2; 
    mergeSortRecursive(list, left, mid); 
    mergeSortRecursive(list, mid + 1, right); 
    merge(list, left, mid, mid + 1, right); 

}

//合并这两个列表

public static <E extends Comparable<E>> void merge(E[] list, int leftFirst, 
     int leftLast, int rightFirst, int rightLast) { 
    @SuppressWarnings("unchecked") 
    E[] mergeList = (E[]) Array.newInstance(list.getClass() 
      .getComponentType(), rightLast - leftFirst + 1); 
    int rightIndex = rightFirst; 
    int leftIndex = leftFirst; 
    int index = 0; 

    while (leftIndex < leftLast && rightIndex < rightLast) { 
     if (list[leftIndex].compareTo(list[rightIndex]) < 0) { 
      mergeList[index] = list[leftIndex]; 
      leftIndex++; 

     } else { 
      mergeList[index] = list[rightIndex]; 
      rightIndex++; 

     } 
     index++; 
    } 
    while (leftIndex < leftLast) { 
     mergeList[index] = list[leftIndex]; 
     index++; 
     leftIndex++; 
    } 
    while (rightIndex < rightLast) { 
     mergeList[index] = list[rightIndex]; 
     index++; 
     rightIndex++; 
    } 
    for (int i = 0; i < list.length; i++) { 
     list[i] = mergeList[i]; 
    } 
}

来源

2014-10-18 Theodore

我查看了你的代码，并认为我已经得到了错误。看起来有一些独立的问题导致程序不能正常工作。

首先，一个小问题：这里是你制作的递归调用代码：

int mid = left + right/2; 
mergeSortRecursive(list, left, mid); 
mergeSortRecursive(list, mid + 1, right); 
merge(list, left, mid, mid + 1, right);

在该行宣布mid运算符优先级是稍微偏离想什么。我认为你的意思是写

int mid = (left + right)/2;

实际上确实找到了这两个元素的平均值。

的IndexOutOfBoundsException你越来越是由于这里这些行：

for (int i = 0; i < list.length; i++) { 
    list[i] = mergeList[i]; 
}

的这里的问题是，list是整个列表，而不仅仅是你试图用这种特殊的呼叫合并的部分。要解决这个问题，你可以像这样改写它：

for (int i = 0; i < mergeList.length; i++) { 
     list[i + leftFirst] = mergeList[i]; 
    }

这只是将您合并到外部合并数组中的部分数据复制回来。

如果你做出这些改变，你会开始得到一些奇怪的NullPointerException s。问题在于，您将范围的左右端点视为包含边界，但您的合并算法将它们视为独占边界。您可以通过在while循环变化的条件解决这个问题：

while (leftIndex <= leftLast && rightIndex <= rightLast) { 
    if (list[leftIndex].compareTo(list[rightIndex]) < 0) { 
     mergeList[index] = list[leftIndex]; 
     leftIndex++; 

    } else { 
     mergeList[index] = list[rightIndex]; 
     rightIndex++; 

    } 
    index++; 
} 
while (leftIndex <= leftLast) { 
    mergeList[index] = list[leftIndex]; 
    index++; 
    leftIndex++; 
} 
while (rightIndex <= rightLast) { 
    mergeList[index] = list[rightIndex]; 
    index++; 
    rightIndex++; 
}

有了这些变化，似乎一切工作！

来源

2015-08-25 22:55:54 templatetypedef

递归合并排序出界异常排序

回答

相关问题