Java合併排序接收錯誤信息

Question

我對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) 

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。當你這樣做時，應該根據documentation引發一個IndexOutOfBoundsException。 （它的確如此）。這是你看到異常的原因。組合ArrayList的大小爲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

這是因爲你有比數組減一的尺寸更大的數組索引發生。數組索引從0開始併到n-1