學術Java int的[]歸併排序反轉一半的輸出

Question

我越來越脫髮這裏試圖找到在Java中，我歸併排序執行錯誤：

Input: 10 9 8 7 6 5 4 3 2 1 
Output: 5 4 3 2 1 10 9 8 7 6 

我在合併陣列之間的印在功能，它給了我這個：

10 9 8 7 6 5 4 3 2 1 
9 10 
6 7 
7 6 8 
8 7 6 10 9 
4 5 
1 2 
2 1 3 
3 2 1 5 4 
5 4 3 2 1 10 9 8 7 6 

我敢肯定，錯誤必須在我的合併功能。 但我很難找到它。

這裏是我的代碼：

class merge1 
{ 
//the array which will get sorted 
static int N = 10; 
static int[] A = new int[N]; 

static int[] cropArray(int[] a) 
{ 
    int[] b = new int[a.length-1]; 
    System.arraycopy(a, 1, b, 0, b.length); 
    return b; 

} 


static int[] merge(int[] left, int[] right) 
{ 
    int[] merged = new int[left.length + right.length]; 
    int i = 0; 

    //loop must go on until both arrays are emptied into merged 
    while(left.length > 0 || right.length > 0) 
    { 
     //first case: both arrays are still filled with elements to compare 
     if(left.length > 0 && right.length > 0) 
     { 
      if(left[0] <= right[0]) //check for the bigger one 
      { 
       merged[i] = left[0]; 
       left = cropArray(left); 
      } 
      else 
      { 
       merged[i] = right[0]; 
       right = cropArray(right); 
      } 

     } 
     else //second case: one of the arrays is empty 
     { 
      if(left.length > 0) 
      { 
       merged[i] = left[0]; 
       left = cropArray(left); 

      } 
      else if(right.length > 0) 
      { 
       merged[i] = right[0]; 
       right = cropArray(right); 
      } 
     } 

     i++; 
    } //while 

    printA(merged, merged.length); 
    return merged; 
} //merge() 

//merg sort recursivly splits the array in half until only one element is left and then merges each half back together in sorted order 
static int[] mergeSort(int[] a) 
{ 

    //STEP 1 
    //exit case if only one element to sort return this element 
    if(a.length <= 1) return a; 


    //STEP 2 
    // split array into half 
    int len = a.length/2; 
    int[] left, right; 

    //check if length is even, if not even integer division will cause loss of data 
    if(a.length % 2 == 0) 
    { 
     //devide into two even halfs 
     left = new int[len]; 
     right = new int[len]; 
    } 
    else 
    { 
     //devide into two uneven halfs 
     left = new int[len]; 
     right = new int[len+1]; 
    } 

    //cycle through a and save out each half 
    //could also use System.arraycopy here as in the merge function 
    for(int i = 0; i < left.length; i++) 
    { 
     left[i] = a[i]; 
    } 

    for(int i = 0; i < right.length; i++) 
    { 
     right[i] = a[i+len]; 
    } 

    //split each half recursivley until only one element is left 
    mergeSort(left); 
    mergeSort(right); 

    //STEP 3 
    //merge sorted halfs and return 
    return merge(right, left); 

} //mergeSort() 


//initalizes the array for the worst case 
//the worst case for merge sort is an array sorted in reverse 
static void init() 
{ 
    int k = N; 

    for(int i = 0; i < A.length; i++) 
    { 
     A[i] = k; 
     k--; 
    } 

}//init() 

//prints the array, used to check if mergeSort is working 
static void printA(int[] a, int n) 
{ 
    for(int i = 0; i < n; i++) 
    { 
     System.out.print(a[i] + " "); 
    } 
    System.out.println(); //break 

} //printA 

public static void main(String[] args) 
{ 

    //test code 
    init(); 
    printA(A,A.length); 
    int [] sorted = mergeSort(A); 
    //printA(sorted, sorted.length); 

    /*//does 2000 sorts with arrays going from 0 to 1999 elements 
    for(int i = 0; i < 2000; i++) 
    { 
     init(); 
     long x = System.nanoTime(); 
     mergeSort(A, i); 
     System.out.println(i + " " + (System.nanoTime() - x)); 
    }*/ 

} //main() 

}//merge1 

Answer 1

你不重新分配在您的通話right和left到mergeSort()，所以實際的「排序」並不攜帶鏈：

而不是

mergeSort(left); 
mergeSort(right); 

你想

left = mergeSort(left); 
right = mergeSort(right); 

Answer 2

我會寫一些psudocode的合併（）函數在這裏

merge(int[] left, int[] right) 
{ 
    int l = 0; 
    int r = 0; 

    int[] merged = new int[left.lentgh+right.length]; 

    for(int i=0; i<merged.length; i++) 
    { 
     // this condition is dependant of the fact that merged.length is equal to the sum of left.length and right.length 
     if(r >= right[r].length || (l < left.length && left[l] < right[r])) 
     { 
      merged[i] = left[l]; 
      l++; 
     } 
     else 
     { 
      merged[r] = right[r]; 
      r++; 
     } 
    } 
    return merged 
}