将合并排序伪代码转换为运行 Java 代码

Question

我试图将此合并排序伪代码转换为 Java 但没有得到正确的输出。这是伪代码：

Merge-Sort(A, p, r )
   if p < r
     then q←(p+r)/2 
     Merge-Sort(A, p, q)
     Merge-Sort(A, q + 1, r )
     Merge(A, p, q, r )


Merge(A, p, q, r )
   for k←1 to r−p+1 do
     if j>r or (i ≤ q and A[i] ≤ A[j])
     then B[k]←A[i]; i←i+1 else B[k]←A[j];j←j+1
   for k←1 to r−p+1 do A[k+p−1]←B[k]

这是我的 Java 代码：

public class 合并排序 {

public static void main(String[] args) {
    int[] a = {2, 6, 3, 5, 1};
    mergeSort(a, 0, a.length - 1);
    for (int i = 0; i < a.length; i++) {
        System.out.print(" " + a[i]);
    }
}

public static void mergeSort(int[] a, int from, int to) {
    final int begin = from, end = to;
    if (begin < end) {
        final int mid = (begin + end) / 2;
        MergeSort.mergeSort(a, begin, mid);
        MergeSort.mergeSort(a,  mid+1, end);
        MergeSort.merge(a, begin, mid, end);
    }
}

private static void merge(int[] a, int from, int mid, int to) {
    final int begin = from, mitte = mid, end = to;

    int[] B = new int[a.length];

    int i = begin, j = mitte;
    for (int k = 0; k <= end-begin; k++) {
        if (j > end || (i <= mitte && a[i] <= a[j])) {
            B[k] = a[i];
            i++;
        } else {
            B[k] = a[j];
            j++;
        }
    }

    for (int k = 0; k < end-begin; k++) {
        a[k + begin] = B[k];
    }
}

遗憾的是，它不是那样工作的。我想我对某些索引做错了，但我无法弄清楚错误到底在哪里。我需要尽可能接近这个伪代码。如果有人能告诉我我做错了什么，那就太好了。

Answer 1

为 Merge 算法给出的伪代码有些不正确，因为它没有说明 只有一个指针移动而其他指针保持静止 的情况。

在上述情况下，您必须通过移动该固定指针来单独填充临时数组。

另外 B 的要求长度是 to - from + 1 应该是 j = mitte + 1 而不是 j = mitte 合并的正确代码是：

private static void merge(int[] a, int from, int mid, int to) {
        final int begin = from, mitte = mid, end = to;

        int[] B = new int[end-begin+1];
        int k=0;
        int i = begin, j = mitte+1;
        while(i<=mid&&j<=end)
            if(a[i]<=a[j]){
                B[k++] = a[i];
                i++;
            } else {
                B[k++] = a[j];
                j++;
            }
        //in case i remained stationary
        while(i<=mid)
            B[k++] = a[i++];

        //in case j remained stationary
        while(j<=end)
            B[k++] = a[j++];

        //Now copy the array
        i=0;
        for(k=begin;k<=end;++k)
         a[k]=B[i++];
    }

将合并排序伪代码转换为运行 Java 代码

Converting Merge Sort pseudocode to running Java code

java

sorting

algorithm

pseudocode

将合并排序伪代码转换为 运行 Java 代码

Converting Merge Sort pseudocode to running Java code

java

sorting

algorithm

pseudocode

将合并排序伪代码转换为运行 Java 代码