遞歸合併排序出界異常排序

我想知道是否有人可以幫我找出爲什麼我在這段代碼中出現了一個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

遞歸合併排序出界異常排序

回答

相關問題