在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中合并排序实施问题

回答

相关问题