在Java中合併排序實施問題

我在算法課程中，並且正在學習合併排序。我們的教授建議我們嘗試實施本書中提供的僞代碼。在Java中合併排序實施問題

我是否在使用Integer.MAX_VALUE的作爲排序整數數組中的標記值時校正（在線路中的合併方法僞代碼以下8 & 9中使用）？
對於Merge-Sort僞代碼方法的第2行，使用Math.ceil（）像Java那樣編寫代碼是否正確？（編輯：它實際上是地板，我更新了我的代碼以反映這一點。）

如果您發現任何其他錯誤，請告訴我！

這裏是本書給合併排序的僞代碼。

而且，這裏是我如何在Java編碼是：

public void mergeSort(int[] arrNums, int p, int r) { 
    if (p < r) { 
     int q = (p + r)/2; 
     mergeSort(arrNums, p, q); 
     mergeSort(arrNums, q + 1, r); 
     merge(arrNums, p, q, r); 
    } 
} 

public void merge(int[] arrNums, int p, int q, int r) { 
    int nOne = q - p + 1; 
    int nTwo = r - q; 

    int[] arrLeft = new int[nOne + 1]; 
    int[] arrRight = new int[nTwo + 1]; 

    for (int i = 0; i < nOne; i++) { 
     arrLeft[i] = arrNums[p + i - 1]; 
    } 

    for (int j = 0; j < nTwo; j++) { 
     arrRight[j] = arrNums[q + j]; 
    } 

    arrLeft[nOne] = Integer.MAX_VALUE; 
    arrRight[nTwo] = Integer.MAX_VALUE; 

    // Tracks arrLeft index 
    int i = 0; 

    // Tracks arrRight index 
    int j = 0; 

    for (int k = p; k < r; k++) { 
     if (arrLeft[i] <= arrRight[j]) { 
      arrNums[k] = arrLeft[i]; 
      i++; 
     } else { 
      arrNums[k] = arrRight[j]; 
      j++; 
     } 
    } 
}

來源

2017-04-01 Nishant

這不是僞代碼中的「ceil」，它是「floor」。如果你用整數進行操作，這就意味着無論如何。 –

使用無窮大的替代方法是檢查左或右數組是否沒有更多變量，然後將另一個數組的其餘部分啞變爲主數組。 –

@ ShadyAtef「啞巴剩下的??」你的意思是「轉儲」？ – ajb

最後for循環在你merge方法，變量k應該從p - 1開始：

for (int k = p - 1; k < r; k++) { 
    if (arrLeft[i] <= arrRight[j]) { 
     arrNums[k] = arrLeft[i]; 
     i++; 
    } else { 
     arrNums[k] = arrRight[j]; 
     j++; 
    } 
}

許多教科書中的僞代碼喜歡從1開始數組索引，所以在這裏你需要減去1.

來源

2017-04-02 00:17:40 shizhz

我在幾天前實現它，如果有人會感興趣。

private static void mergeSort(double[] arr, int start, int end){ 
    if(start < end){ 
     int mid = (start + end)/2; 
     mergeSort(arr, start, mid); 
     mergeSort(arr, mid + 1, end); 
     Merge(arr, start, mid, end); 
    } 
} 


private static void Merge(double[] arr, int start, int mid, int end){ 

    double[] leftArray = new double[mid - start + 2]; 
    double[] rightArray = new double[end - mid + 1]; 
    for(int i = start; i <= mid; i++) 
     leftArray[i - start] = arr[i]; 
    for (int i = mid + 1; i <= end; i++) 
     rightArray[i - mid - 1] = arr[i]; 

    leftArray[mid - start + 1] = Double.POSITIVE_INFINITY; 
    rightArray[end - mid] = Double.POSITIVE_INFINITY; 

    int leftIndex = 0, rightIndex = 0; 

    for (int k = start; k <= end; k++){ 
     if(leftArray[leftIndex] <= rightArray[rightIndex]) 
      arr[k] = leftArray[leftIndex++]; 
     else 
      arr[k] = rightArray[rightIndex++]; 
    } 
}

來源

2017-08-20 13:53:55 sheldonzy

在Java中合併排序實施問題

回答

相關問題