有人可以指出合併函數中的錯誤

Question

運行代碼它顯示IndexOutBoundException 我不知道它爲什麼會發生。這與合併函數有關。

public class MergeSort { 

    public static <T extends Comparable<T>> void sort(List<T> lst) { 
     System.out.println(lst.size()); 

     mergeSort(lst, 0, lst.size() - 1); 

    } 

    private static <T extends Comparable<T>> void mergeSort(List<T> l, int low,int high) { 

     if (low < high) { 
      int mid = low +((high-low)/2); 
      mergeSort(l, low, mid); 
      mergeSort(l, mid + 1, high); 
      merge(l, low, high, mid); 

     } 
    } 

    private static <T extends Comparable<T>> void merge(List<T> lst, int low,int high, int mid) { 
     List<T> temp = new ArrayList<T>(); 

     for (int i = low; i <= high; i++) { 
      System.out.println(lst.get(i)); 
      temp.add(i,lst.get(i)); 
     } 

     System.out.println(); 

     int i = low; 
     int j = mid + 1; 
     int k = low; 
     while (i <= mid && j <= high) { 
      if ((temp.get(i)).compareTo(temp.get(j)) <= 0) { 
       lst.set(k, temp.get(i)); 
       i++; 
      } else { 
       lst.set(k, temp.get(j)); 
       j++; 
      } 
      k++; 
     } 
     while (i <= mid || j <= high) { 
      if (i <= mid) { 
       lst.set(k, temp.get(i)); 
       k++; 
       i++; 
      } else if (j <= high) { 
       lst.set(k, temp.get(j)); 
       k++; 
       j++; 
      } 
     } 
     for(T e:lst){ 
      System.out.print(e+ " "); 
     } 
     System.out.println(); 
    } 

錯誤是：

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 3, Size: 0 
    at java.util.ArrayList.rangeCheckForAdd(ArrayList.java:643) 
    at java.util.ArrayList.add(ArrayList.java:455) 
    MergeSort.merge(MergeSort.java:34) 
    MergeSort.mergeSort(MergeSort.java:22) 
    MergeSort.mergeSort(MergeSort.java:21) 
    MergeSort.mergeSort(MergeSort.java:20) 
    MergeSort.sort(MergeSort.java:11) 
    Main.main(Main.java:65) 

Answer 1

你的異常被拋出就行

temp.add(i,lst.get(i)); 

那是因爲你試圖設置列表中的值不存在的索引。變量temp指向一個空列表;因此，對高於0的索引進行的任何分配將拋出IndexOutOfBoundsException。這被記錄在List接口：

void add(int index, E element)

插入此列表（可選操作）中指定位置的指定的元素。將當前位置的元素（如果有的話）和任何後續元素移到右側（將其中的一個添加到它們的索引）。

[...]

拋出：

[...]

IndexOutOfBoundsException - 如果索引超出範圍(index < 0 || index > size())

一個簡單的解決問題的方法雖然不是最有效的，但是在創建後立即使用空值初始化臨時列表，然後set而不是add的相關值。

private static <T extends Comparable<T>> void merge(List<T> lst, int low, 
    int high, int mid) { 

    List<T> temp = new ArrayList<T>(); 

    // Fill temp list with empty values 
    for(int i=0; i<lst.size(); i++){ 
     temp.add(null); 
    } 

    // Set the values we are going to work on. 
    for (int i = low; i <= high; i++) { 
     System.out.println(lst.get(i)); 
     temp.set(i,lst.get(i)); 
    } 

    ... 
} 

Answer 2

IndexOutOfBoundsException異常意味着很簡單，你試圖訪問一個不存在的元素。嘗試檢查是否存在之前，事情存在。

錯誤告訴你，即使列表大小爲零，您仍然試圖訪問索引3處的元素。