在我的 Java 合并排序函数中，即使条件为假，它也会进入循环。为什么？

Question

在我的"merge"函数中，在while循环中，给定的条件是a!=null && b!=null，但是当b为null时，还是进入了while循环，后面给出了一个错误。

int[] merge(int[]a, int[]b)
{
    int length = a.length+b.length;
    int[]c = new int[length];
    while (a!=null && b!=null)
    {
        if (a[0]<b[0])
        {
            c[length-1]=a[0];
            a = tail(a);
        }
        else
        {
            c[length-1]=b[0];
            b = tail(b);
        }
    }
    return c;
}

int[] mergeSort(int[]a)
{
    if (a.length==1)
        return a;

    int[] q = new int[a.length];
    int[] l = new int[a.length/2];
    int [] r = new int[a.length-l.length];

    for (int i=0; i<l.length; i++)
    {
        l[i] = a[i];
    }
    for (int i=l.length; i<r.length; i++)
    {
        r[i-l.length] = a[i];
    }
    q = merge(mergeSort(l), mergeSort(r));
    return q;
}

Answer 1

我认为，您遇到的情况是其中一个数组（a 或 b）已经为空，而另一个数组仍然有元素。所以，在 merge 函数中你应该考虑到这一点。

这是您的 mergeSort:

的完整实现

public class Answer {

  public static void main(String[] args) {
    int[] unsorted = new int[]{4,3,4,2,1,1,3,3,3,3,3,5,6,6,9,9,10,7,7,8};
    System.out.println(Arrays.toString(mergeSort(unsorted)));
  }

  public static int[] mergeSort(int[]a) {
    if (a.length == 1) return a;

    int[] q = new int[a.length];
    int[] l = new int[a.length / 2];
    int [] r = new int[a.length - l.length];

    for (int i = 0; i < l.length; i++) {
      l[i] = a[i];
    }

    for (int i = 0; i < r.length; i++) {
      r[i] = a[l.length + i];
    }

    q = merge(mergeSort(l), mergeSort(r));
    return q;
  }

  private static int[] merge(int[]a, int[]b) {
    int length = a.length + b.length;
    int[] c = new int[length];
    int p = 0;
    while (a.length > 0 && b.length > 0) {
      if (a[0] < b[0]) {
        c[p++] = a[0];
        a = tail(a);
      } else {
        c[p++] = b[0];
        b = tail(b);
      }
    }
    while (a.length > 0) {
       c[p++] = a[0];
       a = tail(a);
    }
    while (b.length > 0) {
       c[p++] = b[0];
       b = tail(b);
    }
    return c;
  }

  private static int[] tail(int[] a) {
    int[] t = new int[a.length - 1];
    for (int i = 0; i < t.length; i++) {
      t[i] = a[i + 1];
    }
    return t;
  }
}

Answer 2

其实你的辅助方法有问题merge()。

我强烈建议您借此机会对您的方法进行系统测试。考虑到我们在编写程序时总是会犯错误，发现错误并加以纠正是工作的一部分。

让事情变得更容易的是预测这个事实：sh*t 发生了。并花时间写下一些测试用例，包括输入数据和预期结果。

int[] empty = {};
int [] r1 = merge(empty, empty);
System.out.println("Result should be empty\n");
printArray(r1);

int [] oneElement = { 23 };
int [] r3 = merge(oneElement, empty);
System.out.println("Result should be [23]\n");
printArray(r2);

...

原来你有自动化测试（代码修改35次以后我们都懒得每次都手动做了°。

这会将您带到 "unit tests"...

在我的 Java 合并排序函数中，即使条件为假，它也会进入循环。为什么？

In my Java merge sort fucntion, even when the condition is false, it is entering the loop. Why?

java

merge

mergesort