Debugging Mergesort Implementation

Question

好的，我知道這個問題沒有顯示研究工作，但我一直在經歷這個代碼很多次，我無法弄清楚我做錯了。我知道有很多Mergesort實現的例子，但我想按照我的方式來做。任何幫助表示讚賞，謝謝。

import java.util.Scanner; 
public class MergeSort 
{ 
    public static int[] mergeSort(int[] arr) 
    { 
     if (arr.length > 1) 
     { 
      int[] arr1 = splitLeft(arr); 
      int[] arr2 = splitRight(arr); 
      arr1 = mergeSort(arr1); 
      arr2 = mergeSort(arr2); 
      return merge(arr1, arr2); 
     } 
     else 
      return arr; 
    } 

    public static int[] splitLeft(int[] arr) 
    { 
     int middle = arr.length/2; 
     int[] newarr = new int[middle]; 
     for (int i = 0; i < middle; i++) 
      newarr[i] = arr[i]; 
     return newarr; 
    } 

    public static int[] splitRight(int[] arr) 
    { 
     int middle = arr.length/2; 
     int[] newarr = new int[arr.length - middle]; 
     for (int i = 0; i + middle < arr.length; i++) 
      newarr[i] = arr[i + middle]; 
     return newarr; 
    } 

    public static int[] merge(int[] arr1, int[] arr2) 
    {  
     int[] sorted = new int[arr1.length+arr2.length]; 

     int i1 = 0; 
     int i2 = 0; 
     int i = 0; 

     while (i1 < arr1.length && i2 < arr2.length) 
     { 
      if (arr1[i1] < arr2[i2]) 
      { 
       sorted[i] = arr1[i1]; 
       i1++; 
      } 

      else 
      { 
       sorted[i] = arr2[i2]; 
       i2++; 
      } 
     i++; 
     } 

     while (i1 < arr1.length) 
     { 
      sorted[i] = arr1[i1]; 
      i1++; 
      i++; 
     } 

     while (i2 < arr2.length) 
     { 
      sorted[i] = arr1[i2]; 
      i2++; 
      i++; 
     } 
     return sorted; 
    } 

    public static int getNum(int x) 
    { 
     int num = (int)(Math.random()*x + 1); 
     return num; 
    } 

    public static void printArr(int[] arr) 
    { 
     System.out.println(); 
     for (int i = 0; i < arr.length; i++) 
      System.out.println(arr[i]); 
    } 

    static Scanner reader = new Scanner(System.in); 
    public static void main(String [ ] args) 
    { 
     int i; 

     System.out.println("Type the length of the array"); 
     int n = reader.nextInt(); 

     System.out.println("Type the range of the random numbers generator"); 
     int range = reader.nextInt(); 

     int[]arr = new int[n]; 

     for (i = 0; i < n; i++) 
      arr[i] = getNum(range); 

     printArr(arr); 

     int[] sorted = new int[n]; 
     sorted = mergeSort(arr); 

     printArr(sorted); 
    } 
} 

Answer 1

我認爲問題出在您的splitRight函數中。考慮以下代碼：

for (int i = middle; i < arr.length; i++) 
    newarr[i] = arr[i]; 

這會嘗試將i個元素從arr複製到的newarr的i個位置，但是這是不正確。例如，如果陣列arr有十大要素，你要的arr複製件5至newArr 0地位，arr元件6定位的newarr 1等

爲了解決這個問題，考慮嘗試這樣的東西：

for (int i = 0; i + middle < arr.length; i++) 
    newarr[i] = arr[i + middle]; 

希望這有助於！

Answer 2

當你

for (int i = middle; i < arr.length; i++) 
      newarr[i] = arr[i]; 

你肯定要求在原數組中的位置，並在同一時間，新數組中尋找他們（這恰好是短）。