Java 中的合并排序实现问题

Question

我正在学习算法课程，正在学习合并排序。我们的教授建议我们尝试实现书中提供的伪代码。

我使用 Integer.MAX_VALUE 作为标记值是否正确对整数数组进行排序（在 Merge 的第 8 行和第 9 行中使用）下面的方法伪代码)?
对于合并排序伪代码方法的第 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++;
        }
    }
}

Answer 1

您的 merge 方法中的最后一个 for 循环，变量 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。

Answer 2

我几天前实现了，如果有人感兴趣的话。

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++];
    }   
}

Java 中的合并排序实现问题

Merge sort implementation questions in Java

java

sorting

algorithm

mergesort

sentinel