合併排序不排序數組

Question

在閱讀合併排序後，我已經編寫了下面的Java代碼。運行代碼時沒有錯誤，但合併排序不排序數組。它只是返回原始的未排序數組。我不能爲了我的生活找出問題的癥結所在。我感謝任何線索。

public class mergeSort { 

public void mergeSort(int array[], int n){ 

    if(n<2) return; 
    int m=n/2; 
    int left[]=new int[m]; 
    int right[]=new int[n-m]; 
    int i; 

    for(i=0; i<m;i++){ 
     left[i]=array[i]; 
    } 
    for(i=m; i<n;i++){ 
     right[i-m]=array[i]; 
    } 
    printArray(left); 
    printArray(right); 
    mergeSort(left, m); 
    mergeSort(right, n-m); 
    merge(array, left, m, right, m-n); 
} 

private void merge(int[] array, int[] left, int leftCount, int[] right, int rightCount) { 
    int i=0,j=0,k=0; 

    while(i<leftCount && j< rightCount){ 
     if(left[i]<=right[j]){ 
      array[k]=left[i]; 
      i++; 
      k++; 
     }else{ 
      array[k]=right[j]; 
      j++; 
      k++; 
     } 
    } 

    while(i<leftCount){ 
     array[k]=left[i]; 
     i++; 
     k++; 
    } 
    while(j<rightCount){ 
     array[k]=right[j]; 
     j++; 
     k++; 
    } 

} 
static void printArray(int arr[]) 
    { 
     int n = arr.length; 
     for (int i=0; i<n; ++i) 
      System.out.print(arr[i] + " "); 
     System.out.println(); 
    } 

public static void main(String[] args){ 
    int a[]={3,2,1,7,9,8}; 
    printArray(a); 


    mergeSort m=new mergeSort(); 
    m.mergeSort(a, a.length); 

    printArray(a); 
} 

}

Answer 1

的leftCount和rightCount您傳遞給合併方法是錯誤的。

相反，不要通過該計算，而是在合併方法中計算。我試着用下面的改變你的代碼，它工作得很好。

merge(array, left, right); 
... 
private void merge(int[] array, int[] left, int[] right) { 
    int i=0,j=0,k=0; 
    int leftCount= left.length; 
    int rightCount = right.length;