如何合并排序？只需要知道我在哪里弄错了

Question

我已经开始在java中编程并试图学习合并排序。我得到了算法，并用它编码。我不明白我错了什么。有人可以帮助我这个了解合并排序和调试此代码。

public class Main { 

    public static void main(String[] args) { 

    // Merge Sort 

    int[] myArray = {2, 4, 1, 6, 8, 5, 3, 7}; 


     mergeSort(myArray); 
     System.out.println((Arrays.toString(myArray))); 
    } 
    public static void mergeSort(int []toSortArray){ 
     int n= toSortArray.length; 
     if (n < 2) { 
     return; 
     } 
    int mid = n/2; 
    int [] Left= new int [mid]; 
    int []Right = new int[n-mid]; 
    for(int i=0;i<mid-1;i++){ 
     Left[i]=toSortArray[i]; 
    } 
    for(int i=mid;i<n-1;i++){ 
     Right[i-mid]=toSortArray[i]; 
    } 
    mergeSort(Left); 
    mergeSort(Right); 
    merge(Left,Right,toSortArray); 

} 

public static void merge(int[] Left, int [] Right, int []SortedArray){ 
    int nL = Left.length; 
    int nR= Right.length; 

    int i=0;//Index position for left array 
    int j=0;// index of position of Right array 
    int k=0;// Index position of sorted Array 

    while (i<nL && j<nR){ 
     if (Left[i]<Right[j]) { 
      SortedArray[k] = Left[i]; 
      i++; 
      k++; 
     } 
     if (Right[j]<Left[i]){ 
      SortedArray[k] = Right[j]; 
      j++; 
      k++; 
     } 
    } 
    while(i<nL){ 
     SortedArray[k]=Left[i]; 
     i++; 
     k++; 
    } while (j<nR){ 
     SortedArray[k]= Right[j]; 
     j++; 
     k++; 
    } 

} 

} 

Answer 1

在归并（）中，两个环以复制数据应该是我<中间（未我<中间-1）和i < N（不我< N-1）。

在merge（）中，第一个if应该是if（Left [i] < = Right [j]）（不仅仅是<）。第二个if（Right [j] < Left [i]）可以替换为else（不需要第二个if）。

下面的代码似乎工作：

package x; 
import java.util.Arrays; 
public class x { 
    public static void main(String[] args) { 
     int[] myArray = {2, 4, 1, 6, 8, 5, 3, 7}; 
    mergeSort(myArray); 
    System.out.println((Arrays.toString(myArray))); 
    } 

    public static void mergeSort(int []toSortArray){ 
     int n= toSortArray.length; 
     if (n < 2) { 
      return; 
     } 
     int mid = n/2; 
     int []Left = new int [mid]; 
     int []Right = new int[n-mid]; 
     for(int i=0;i<mid;i++){ 
      Left[i]=toSortArray[i]; 
     } 
     for(int i=mid;i<n;i++){ 
      Right[i-mid]=toSortArray[i]; 
     } 
     mergeSort(Left); 
     mergeSort(Right); 
     merge(Left,Right,toSortArray); 
    } 

    public static void merge(int[] Left, int [] Right, int []SortedArray){ 
     int nL = Left.length; 
     int nR= Right.length; 

     int i=0;// index position for Left array 
     int j=0;// index position for Right array 
     int k=0;// index position for Sorted array 

     while (i<nL && j<nR){ 
      if (Left[i]<=Right[j]) { 
       SortedArray[k] = Left[i]; 
       i++; 
       k++; 
      } else { 
       SortedArray[k] = Right[j]; 
       j++; 
       k++; 
      } 
     } 
     while(i<nL){ 
      SortedArray[k]=Left[i]; 
      i++; 
      k++; 
     } while (j<nR){ 
      SortedArray[k]= Right[j]; 
      j++; 
      k++; 
     } 
    } 
}