合併排序從文件中讀取數據

Question

我的代碼有什麼問題？我正在從每行包含1個數字的文件讀取數據，並使用合併排序對其進行排序。我收到以下錯誤：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3 
     at MergeSort.merge(MergeSort.java:67) 
     at MergeSort.sort(MergeSort.java:30) 
     at MergeSort.main(MergeSort.java:86) 

文本文件：

300 
40 
512 
234 
100 

這有什麼錯我的歸併執行？

這裏是我的代碼：

import java.io.BufferedReader; 
import java.io.FileInputStream; 
import java.io.IOException; 
import java.io.InputStream; 
import java.io.InputStreamReader; 

public class MergeSort 
{ 
    void sort(int[] arr, int low, int high) 
    { 
     if(high > low) 
     { 

     int mid = (low + high)/2; 
     sort(arr,low,mid); 

     sort(arr,mid+1,high); 

     merge(arr, low, mid+1, high); 
     } 
    } 
    void merge(int arr[], int low,int mid, int high) 
    { 
     int helper[] = new int[arr.length]; 

     //copy both halves into helper 
     for(int i=0;i< arr.length;i++) 
     { 
      helper[i] = arr[i]; 
     } 

     //compare elements from left & right, initialize variables 
     int helperLeft = low; 
     int helperRight = high; 
     int curr = mid+1; 

     //while if left<=mid && mid+1 <=right && if left < right assign lowest elem to original array 
     while(helperLeft <= curr && curr <=helperRight) 
     { 
      if(helperLeft <= curr) 
      { 
       arr[helperLeft] = helperLeft; 
       helperLeft++; 
      } 
      else 
      { 
       arr[curr] = curr; 
       curr++; 
      } 
      helperRight++; 
     } 
     //copy all elements to arr 
     int rem = mid-helperLeft; 
     for(int i=0;i<rem;i++) 
     { 
      arr[helperRight+i] = helper[helperLeft+i]; 
     } 
    } 

    public static void main(String[] args) throws NumberFormatException, IOException { 
     // TODO Auto-generated method stub 

     MergeSort pb = new MergeSort(); 

     InputStream inputStream = new FileInputStream("task.txt"); 
     @SuppressWarnings("resource") 
     BufferedReader R = new BufferedReader(new InputStreamReader(inputStream)); 
     int arraySize = Integer.parseInt(R.readLine()); 
     int[] inputArray = new int[arraySize]; 
     for (int i = 0; i < arraySize; i++) { 
      inputArray[i] = Integer.parseInt(R.readLine()); 
     } 

     pb.sort(inputArray, 0, inputArray.length-1); 

     for (int j = 0; j < inputArray.length; j++) { 
      System.out.println(inputArray[j]); 
     } 
    } 
} 

新的異常：

Exception in thread "main" java.lang.NumberFormatException: null 
    at java.lang.Integer.parseInt(Unknown Source) 
    at java.lang.Integer.parseInt(Unknown Source) 
    at coursera.MergeSort.main(MergeSort.java:74) 

Answer 1

試試這個：

import java.io.BufferedReader; 
import java.io.FileReader; 
import java.io.IOException; 
import java.util.ArrayList; 
import java.util.List; 

public class MergeSort {  
    public void mergeSort(Integer[] array, int lo, int n) { 
     int low = lo; 
     int high = n; 
     if (low >= high) { 
      return; 
     } 

     int middle = (low + high)/2; 
     mergeSort(array, low, middle); 
     mergeSort(array, middle + 1, high); 
     int end_low = middle; 
     int start_high = middle + 1; 
     while ((lo <= end_low) && (start_high <= high)) { 
      if (array[low] < array[start_high]) { 
       low++; 
      } else { 
       int Temp = array[start_high]; 
       for (int k = start_high - 1; k >= low; k--) { 
        array[k + 1] = array[k]; 
       } 
       array[low] = Temp; 
       low++; 
       end_low++; 
       start_high++; 
      } 
     } 
    } 

    public static void main(String[] args) throws NumberFormatException, IOException { 
     MergeSort pb = new MergeSort(); 
     try { 
      BufferedReader br = new BufferedReader(new FileReader("E:\\task.txt")); 
      List<Integer> lines = new ArrayList<Integer>(); 
      String line; 
      while ((line = br.readLine()) != null) { 
       lines.add(Integer.parseInt(line)); 
      } 
      br.close(); 
      Integer[] inputArray = lines.toArray(new Integer[lines.size()]); 
      pb.mergeSort(inputArray, 0, inputArray.length - 1); 
      for (Integer i : inputArray) { 
       System.out.println(i); 
      } 
     } catch (IOException ie) { 
      System.out.print(ie.getMessage()); 
     } 

    } 
} 

Answer 2

我認爲這個問題是在while條件

while(helperLeft <= curr && curr <=helperRight) 

在此，你永遠不會檢查是否helperLeft或helperRight超出了數組索引。將其修改爲如下：

while(helperLeft < arr.length 
    && helperRight< arr.length 
    && helperLeft <= curr 
    && curr <=helperRight) 
{ 
    // do something 
} 

Answer 3

除了例外情況，我認爲您的merge邏輯是正確的。看看你的代碼：

while(helperLeft <= curr && curr <=helperRight) 
     { 
      if(helperLeft <= curr) 
      { 
       arr[helperLeft] = helperLeft; 
       helperLeft++; 
      } 
      else 
      { 
       arr[curr] = curr; 
       curr++; 
      } 
      helperRight++; 
     } 

這裏，helperLeft，helperRight和curr都是數組索引。您正在設置索引的數組元素，如a[23]=23。這是不正確的。在MergeSort的合併中，我們應該比較來自左側和右側的元素並進行合併，而不是索引。

我建議爲你的mergesort編寫一個unittest，以確保它適用於所有情況（包括角落案例），然後在你的真實代碼中調用你的方法。

如果你的MergeSort.sort（）是靜態的，它也會好嗎？

我實現了一個合併（）也一樣，你可以點擊這裏：https://github.com/sk1418/jalgorithm/blob/master/src/main/java/com/kent/algorithm/sorting/MergeSort.java#L130

希望它幫助。