合并排序 Java 实现，因此合并在一个数组中工作，第二个拆分数组反转

Question

挑战：在关于数据结构和算法的讲座中，我遇到了合并排序的一个版本，它使用合并例程的方式是，后半部分与拆分索引相反，然后从那里比较第一个和最后一个元素。我试图在 java 中实现，但它总是以某种方式失败。

问题：正在对数组进行排序，因此输出为 [1, 2, 4, 8, 6]，因此 6 未排序。递归调用似乎没有在最后一次 merge 调用中查看元素 6。

我的尝试：移动不同的索引并添加不同的打印语句以进行检查。我试图在 merge 中的最后一个 for 循环之前使 j = r 每次都导致 堆栈溢出 。我试图改变计算数组大小的方式，因为我不确定伪代码是否将数组从 1 或 0 开始。我试图将 if(p < r-1) 转移到 if(p <= r-1)但出现 堆栈溢出.

我查看了 java 合并例程的不同实现，到目前为止我发现的每一个似乎都适用于两个数组。上面的方法不能正常工作是否有严重的原因，或者知道如何解决这个问题？

给出以下伪代码：

void merge_sort(array<T>& A, int p, int r) {
    if (p < r - 1) {
        int q = Floor((p + r) / 2);
        merge_sort(A, p, q);
        merge_sort(A, q + 1, r);
        merge(A, p, q, r);
    }
}

void merge(array<T>& A, int p, int q, int r) {
    array<T> B(p, r - 1);
    int i, j;
    for (i = p; i < q; i++)
        B[i] = A[i];
    // Now i=q
    for (j = r; i < r; i++)
        B[--j] = A[i];
    i = p;
    j = r - 1;
    for (int k = p; k < r; k++)
        A[k] = (B[i] < B[j]) ? B[i++] : B[j--];
}

我试着在 java 中这样实现：

import java.util.Arrays;

public class Mergesort {

    private static int[] A = new int[]{ 4, 2, 1, 8, 6 };

    public static void main(String[] args) {
        merge_sort(0, A.length - 1);
        System.out.println(Arrays.toString(A));
    }

    public static void merge_sort(int p, int r) {
        if (p < r - 1) {
            int q = Math.floor((p + r) / 2);
            merge_sort(p, q);
            merge_sort(q + 1, r);
            merge(p, q, r);
        }
    }

    public static void merge(int p, int q, int r) {
        int[] B = new int[r - p];
        int i, j;
        for (i = p; i < q; i++)
            B[i] = A[i]
        for (j = r; i < r; i++)
            B[--j] = A[i];
        i = p;
        j = r - 1;
        for (int k = p; k < r; k++)
            A[k] = (B[i] < B[j])? B[i++] : B[j--];
    }
}

Answer 1

您的代码中存在多个问题：

临时数组太短：因为r是最后一个元素的索引，所以大小应该是r - p + 1。将 r 作为要排序的切片的最后一个元素之后的索引传递要简单得多。
第一个 for 循环不正确：您应该在 B 和 A 中使用不同的索引。
第二个for循环向下复制到B[r - 1]，但应该使用B[r - p]。
合并循环不正确：您应该在访问 B[i] and/or [=24 之前测试 i 和 j 是否仍在各自的边界内=].
[minor] java 中不需要 int q = Math.floor((p + r) / 2); 因为 p 和 r 的类型是 int，所以除法将使用整数运算。

这是修改后的版本：

public class Mergesort {

    private static int[] A = new int[]{ 4, 2, 1, 8, 6 };

    public static void main(String[] args) {
        merge_sort(0, A.length);
        System.out.println(Arrays.toString(A));
    }

    public static void merge_sort(int p, int r) {
        if (r - p >= 2) {
            int q = p + (r - p) / 2;
            merge_sort(p, q);
            merge_sort(q, r);
            merge(p, q, r);
        }
    }

    public static void merge(int p, int q, int r) {
        int m = q - p;  // zero based index of the right half
        int n = r - p;  // length of the merged slice
        int[] B = new int[n];
        int i, j, k;
        for (i = p, j = 0; j < m; j++)
            B[j] = A[i++];
        for (i = r, j = m; j < n; j++)
            B[j] = A[--i];
        for (i = 0, j = n, k = p; k < r; k++) {
            // for stable sorting, i and j must be tested against their boundary
            // A[k] = (i < m && (j <= m || B[i] <= B[j - 1])) ? B[i++] : B[--j];
            // stability is not an issue for an array of int
            A[k] = (B[i] <= B[j - 1]) ? B[i++] : B[--j];
        }
    }
}

反转后半部分允许更简单的合并循环，无需边界测试。但是请注意，有一种更简单的方法可以使用更少的内存并且可能更有效：

    public static void merge(int p, int q, int r) {
        int m = q - p;  // length of the left half
        int[] B = new int[m];
        int i, j, k;
        // only save the left half
        for (i = p, j = 0; j < m; j++)
            B[j] = A[i++];
        for (i = 0, j = q, k = p; i < m; k++) {
            A[k] = (j >= r || B[i] <= A[j]) ? B[i++] : A[j++];
        }
    }

合并排序 Java 实现，因此合并在一个数组中工作，第二个拆分数组反转

Merge Sort Java Implementation so merge works within one array with second splitted array reversed

java

arrays

sorting

mergesort