合并排序算法逻辑的合并功能是错误的

Question

我正在尝试在 Java 中实施合并排序。我了解算法，但在实现时遇到了问题。这是我写的代码：

package sort;

import java.util.Arrays;

public class MergeSort {

public MergeSort() {

}

public static void main(String[] args) {

    int[] d = {26,14,72,34,622,483};
    MergeSort ms = new MergeSort();
    int[] results = ms.mergesort(d);
    for (int i = 0; i < results.length; i++) {
        System.out.println(results[i]);
    }

}

public int[] mergesort(int[] a) {

    System.out.println("Another call to merge sort");

    if (a.length <= 1) { return a;}

    int mid = a.length / 2;
    int[] left = Arrays.copyOfRange(a,0,mid);
    int[] right = Arrays.copyOfRange(a,mid + 1,a.length);

    left = mergesort(left);
    right = mergesort(right);

    int[] result = merge(left,right);
    return result;
}

private int[] merge(int[] b, int[] c) {
    System.out.println("Another call to merge");

    int[] result = new int[b.length+c.length];

    if (b.length == 0) {
        return c;
    } else if (c.length == 0) {
        return b;
    } else if (b[0] < c[0] && b.length == 1) {
        result[0] = b[0];
        for (int i = 1; i < result.length; i++) {
            result[i] = c[i -1];
        }
        return result;
    }else if (b[0] > c[0] && c.length == 1) {
        result[0] = c[0];
        for (int i = 0; i < result.length; i++) {
            result[i] = b[i-1];
        }
        return result;
    }
    else if (b[0] < c[0]) {
        result[0] = b[0];
        result = merge(result,merge(Arrays.copyOfRange(b,1,b.length),c));
        return result;
    } else if (b[0] > c[0]) {
        result[0] = c[0];
        result = merge(result,merge(b,Arrays.copyOfRange(c,1,c.length)));
        return result;
    } else {
        System.out.println("Fell to the bottom.");
        return result;
    }
}

}

问题出在我的合并函数上。我试着按照这里的算法：http://discrete.gr/complexity/ 但我一直得到 IndexOutOfBoundsExceptions 因为如果数组的大小只有 1，那么 Arrays.copyOfRange 就没有索引 1 可以获取。我试图在我的代码中解决这个问题，但它变得非常混乱。按照现在的方式，它会向下调用很多函数，然后抛出一个 IndexOutOfBoundsException。我真的很感激这方面的帮助。而且我只是自己做这个来尝试弄清楚，而不是作为家庭作业。

Answer 1

我建议迭代而不是递归地实现合并。在您的示例中使用的 merge 也是一个错误的 concat 函数，令人困惑（至少将其移至单独的函数）。

在你的情况下，错误在这里：

    for (int i = 0; i < result.length; i++) {
        result[i] = b[i-1];
    }

i 需要从 1 开始，否则 i - 1 == -1 永远不是有效索引。

以后，请注意您的问题中出现异常的位置，并通过调试器运行您的程序，在这种情况下它会立即显示问题。

编辑：好的，这仍然没有产生正确的程序。其他错误：

int[] right = Arrays.copyOfRange(a,mid + 1,a.length);
// needs to be "mid", not "mid + 1", read the doc on the function

EDIT2：最后几行需要是：

else if (b[0] < c[0]) {
    result = merge(new int[]{b[0]},merge(Arrays.copyOfRange(b,1,b.length),c));
    return result;
} else if (b[0] > c[0]) {
    result = merge(new int[]{c[0]},merge(b,Arrays.copyOfRange(c,1,c.length)));
    return result;
} else {

否则，结果会很长。

合并排序算法逻辑的合并功能是错误的

merge function of merge sort algorithm logic is wrong

java

arrays

algorithm

mergesort