java方法返回null，但不应该

Question

我遇到了以下java类的问题。排序算法的工作原理是，但每次返回时都会返回一个空数组（“合并”方法中的返回值）。我试图用大量的System.out.println（）输出检查算法以找出错误，但它看起来像算法的工作。只有最后一个返回会清除已排序的数组并返回一个空数组。我不知道为什么，也不知道如何解决这个问题。 会很好，如果任何人都可以看看并给出提示。 :)

public final class TestClass { 

    private TestClass() { 
     System.exit(-1); // not used 
    } 

    public static <T> T[] mergeSort(final T[] q, final Comparator<T> c) { 
     if (size(q) > 1) { 
      @SuppressWarnings("unchecked") 
      T[] q2 = (T[]) new Object[size(q)]; 
      split(q, q2); 
      T[] left = mergeSort(q, c); 
      T[] right = mergeSort(q2, c); 
      return merge(left, right, c); 
     } else { 
      return q; 
     } 
    } 

    private static <T> T[] merge(final T[] q1, final T[] q2, final Comparator<T> c) { 
     @SuppressWarnings("unchecked") 
     T[] q = (T[]) new Object[size(q1) + size(q2)]; 

     while (size(q1) > 0 || size(q2) > 0) { 
      if (size(q2) == 0 || size(q1) > 0 && c.compare(getElement(q1), getElement(q2)) <= 0) { 
       add(q, getElement(q1)); 
       remove(q1, getElement(q1)); 
      } else { 
       add(q, getElement(q2)); 
       remove(q2, getElement(q2)); 
      } 
     } 
     return q; //returns an empty array on last run?! 
    } 

    private static <T> void split(T[] q1, T[] q2) { 
     while (size(q1) > size(q2)) { 
      add(q2, getElement(q1)); 
      remove(q1, getElement(q1)); 
     } 
    } 

    // add element 
    private static <T> void add(final T[] q1, T pElement) { 
     if (!isFull(q1)) { 
      for (int i = 0; i < q1.length; i++) { 
       if (q1[i] == null) { 
        q1[i] = pElement; 
        break; 
       } 
      } 
     } 
    } 

    // remove element 
    private static <T> void remove(final T[] q1, T pElement) { 
     for (int i = 0; i < q1.length; i++) { 
      if (q1[i] == pElement) { 
       q1[i] = null; 
       break; 
      } 
     } 
    } 

    // is full? 
    private static <T> boolean isFull(final T[] q1) { 
     for (T element : q1) { 
      if (element == null) { 
       return false; 
      } 
     } 
     return true; 
    } 

    // is empty? 
    private static <T> boolean isEmpty(final T[] q1) { 
     for (T element : q1) { 
      if (element != null) { 
       return false; 
      } 
     } 
     return true; 
    } 

    // size 
    private static <T> int size(final T[] q1) { 
     int counter = 0; 
     for (T element : q1) { 
      if (element != null) { 
       counter++; 
      } 
     } 
     return counter; 
    } 

    // get first element of array 
    private static <T> T getElement(final T[] q1) { 
     if (!isEmpty(q1)) { 
      for (int i = 0; i < q1.length; i++) { 
       if (q1[i] != null) { 
        return q1[i]; 
       } 
      } 
     } 
     return null; 
    } 
} 

有一个junit测试，但我每次都得到一个错误，因为结果是一个空的数组。

public class Test { 

    @Test 
    public void testSorting() { 
    final Integer[] list = {5, 1, 3, 2, 8, 1, 3, 9, 5, 0}; 
     TestClass.mergeSort(list, (i, j) -> i - j); 
     assertArrayEquals(new Integer[] {0, 1, 1, 2, 3, 3, 5, 5, 8, 9}, list); 
    } 
} 

Answer 1

你的排序算法工作正常，并且都merge和mergeSort返回正确的结果。但他们都不是就地！他们创建新的数组，并“清空”源数组，将它们的元素设置为null。因此，您的原始list最后只包含null，并且排序的阵列位于您从不使用的调用mergeSort的结果中。

因此，你只需要的mergeSort结果重新分配回一些变量：

final Integer[] list = {5, 1, 3, 2, 8, 1, 3, 9, 5, 0}; 
Integer[] res = mergeSort(list, (i, j) -> i - j); 
System.out.println(Arrays.asList(list)); 
// [null, null, null, null, null, null, null, null, null, null] 
System.out.println(Arrays.asList(res)); 
// [0, 1, 1, 2, 3, 3, 5, 5, 8, 9] 

如果你想使这个就地，这将是一个重大的重新写入。我建议你首先删除所有new Object[]行并将参数int from, int to同时添加到sort和merge方法中，并查看从哪里获得的位置。

事实上，on closer inspection，合并排序似乎不是很就地友好的，因为它是很难合并就地，因为子阵必须保持排序状态。如果你想就地排序，我建议使用Quick Sort。