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。