В моей функции сортировки слиянием Java, даже когда условие ложно, оно входит в цикл.Зачем?

Question

В моей функции "слияния" в цикле while задано условие a!=null && b!=null, но когда b равно нулю, оно все равно входит в цикл 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

На самом деле у вас есть проблема со вспомогательным методом merge().

Я настоятельно рекомендую вам использовать это как возможность практиковать систематическое тестирование ваших методов.Учтите, что все мы постоянно совершаем ошибки, когда пишем программы, и выявление ошибок для их исправления является реальной частью работы.

Что облегчает задачу, так это предвидение по этому поводу: дерьмо случается,И найдите время, чтобы записать несколько тестовых случаев, с входными данными и ожидаемыми результатами.

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-й модификациикод °.

Это приведет вас к «модульным тестам» ....

Answer 2

Я думаю, вы сталкиваетесь с ситуацией, когда один из массивов (либо 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;
  }
}