java中的遞歸mergesort的小捻

-3

我想在java中編寫mergesort程序。不幸的是，我的實現給出了一個零列表作爲代碼的結果。我無法找到這個問題，因爲一切都看起來符合邏輯，並且對我來說是正確的。如果有人能幫我找到這個問題，我將不勝感激。java中的遞歸mergesort的小捻

的代碼如下：

package com.company; 

public class Main { 

public static void main(String[] args) { 
    int[] array = {35,43,21,4,23,1,13,44}; 

    System.out.println("initial array is equal to:"); 
    for (int data:array) { 
     System.out.println(data); 
    } 
    mergeSort(array, new int[array.length], 0, array.length-1); 
    System.out.println("Sorted array is equal to: "); 
    for (int s:array) { 
     System.out.println(s); 
    } 
    // arr = {35,43,21,4,23,1,13,44} 
} 

public static void mergeSort(int[] array,int[] secondaryArray,int leftStart, int rightEnd){ 
    if(leftStart >= rightEnd){ 
     return; 
    } 
    int midPoint = (leftStart + rightEnd)/2; 
    //sorting the left array 
    mergeSort(array, secondaryArray, leftStart, midPoint); 
    //sorting the right array 
    mergeSort(array, secondaryArray, midPoint+1, rightEnd); 
    //merging the sorted left and right array 
    mergeHalves(array, secondaryArray,leftStart, rightEnd); 
} 

public static void mergeHalves(int[] array, int[] secondaryArray, int leftStart, int rightEnd){ 

    int leftEnd = (leftStart + rightEnd)/2; 
    int rightStart = leftEnd + 1; 
    int index = 0; 

    while ((leftStart <= leftEnd) && (rightStart <= rightEnd)){ 
     if(array[leftStart] <= array[rightStart]){ 
      secondaryArray[index] = array[leftStart]; 
      leftStart++; 
     }else { 
      secondaryArray[index] = array[rightStart]; 
      rightStart++; 
     } 
     index++; 
    } 

    System.arraycopy(array,rightStart,secondaryArray,index,rightEnd-rightStart+1); 
    System.arraycopy(array,leftStart,secondaryArray,index,leftEnd-leftStart+1); 
    System.arraycopy(secondaryArray,0,array,0,secondaryArray.length); 

} 
}

來源

2017-08-13 user4353393

你應該做一些調試。 –

您在mergeHalves有一個小bug-，最終陣列副本

System.arraycopy(secondaryArray,0,array,0,secondaryArray.length);

時，應當（假設leftStartCopy是leftStart的副本中mergeHalves不變）：

System.arraycopy(secondaryArray,0,array,leftStartCopy,rightEnd-leftStartCopy+1);

問題是，您正在將所有secondaryArray複製到array，而不是僅相關的單元格。這就是導致array滿了0的原因。

這裏是mergeHalves的全碼：

public static void mergeHalves(int[] array, int[] secondaryArray, int leftStart, int rightEnd){ 
int leftStartCopy = leftStart; 
int leftEnd = (leftStart + rightEnd)/2; 
int rightStart = leftEnd + 1; 
int index = 0; 

while ((leftStart <= leftEnd) && (rightStart <= rightEnd)){ 
    if(array[leftStart] <= array[rightStart]){ 
     secondaryArray[index] = array[leftStart]; 
     leftStart++; 
    }else { 
     secondaryArray[index] = array[rightStart]; 
     rightStart++; 
    } 
    index++; 
} 

System.arraycopy(array,rightStart,secondaryArray,index,rightEnd-rightStart+1); 
System.arraycopy(array,leftStart,secondaryArray,index,leftEnd-leftStart+1); 
System.arraycopy(secondaryArray,0,array,leftStartCopy,rightEnd-leftStartCopy+1);}

來源

2017-08-13 12:38:17

leftStart等於零，不是嗎？如果它是真的，那麼順便寫零或者leftStart – user4353393

並不重要，我試着實現你提到的，但是我再次去了0 – user4353393

不，leftStart是每次mergeHalves被調用時都是不同的（合併點的排序是每次處理數組的不同部分）。此外，leftStart在mergeHalves執行過程中發生更改。 –

嘗試運行與控制你，看看你會得到什麼樣的投入每一個部分。例如，使用不同的輸入數組運行mergeHalves，看看你是否能得到你所期望的。

你可以做的另一件事是讓mergeHalves每次打印它的輸入和最終結果。然後用小樣本調用mergeSort（空數組，具有1個元素的數組，具有2個元素的數組等等），你很快就會明白你的代碼實際上在做什麼。

來源

2017-08-13 11:55:00 orip

java中的遞歸mergesort的小捻

回答

相關問題