java 方法 returns null 但不应该

Question

我遇到以下问题 java Class。排序算法有效，但每次末尾都是空数组时 returns（"merge" 方法中的 return）。我尝试使用大量 System.out.println() 输出来检查算法以查找错误，但看起来该算法有效。只有最后一个 return 清除排序后的数组，而 return 是一个空数组。我不知道为什么，也不知道如何解决。如果有人可以看一下并给出提示，那就太好了。 :)

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 return 都是正确的结果。但他们都到位！他们创建新数组和 "empty" 源数组，将它们的元素设置为 null。因此，您的 original list 仅包含末尾的 null ，排序后的数组位于 result调用您从未使用过的 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[] 行并向 sort 和 merge 方法添加参数 int from, int to 开始，看看您从那里得到什么。

事实上，on closer inspection, Merge Sort seems not to be very in-place friendly, since it is difficult to merge in-place, since the sub-arrays have to remain sorted. If you want to sort in-place, I suggest using Quick Sort.

java 方法 returns null 但不应该

java method returns null but should not

java

arrays

algorithm

mergesort