1

我的合并排序似乎无法正常工作。当我显示排序列表时，它没有排序并添加元素，应该有 9 的地方有 49。有人知道我哪里出错了吗？

public static <E extends Comparable<E>> void mergeSort(List<E> A) {
    int n = A.size();
    if (n > 1) {
        int half = n / 2;
        List<E> B = copyPartialArray(A, 0, half);
        List<E> C = copyPartialArray(A, half, n);
        mergeSort(B);
        mergeSort(C);
        merge(B, C, A);
    }
}

public static <E extends Comparable<E>> void merge(List<E> B, List<E> C, List<E> A) {
    int n1 = B.size();
    int n2 = C.size();
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < n1 && j < n2) {
        if (B.get(i).compareTo(C.get(j)) < 0) {
            A.add(k, B.get(i));
            i++;
        }
        else {
            A.add(k, C.get(j));
            j++;
        }
        k++;
    }
    if (i == n1)
        for (int p = j; p < n2; p++) {
            A.add(k, C.get(p)); k++;
        }
    else if (j == n2)
        for (int p = i; p < n1; p++) {
            A.add(k, B.get(p)); k++;
        }
}

private static <E extends Comparable<E>> List<E> copyPartialArray(List<E> A, int first, int last) {
    int n = last - first;
    List<E> copy = new ArrayList<E>(n);
    for (int i = 0; i < n; i++)
    copy.add(i, A.get(first + i));
    return copy;
}
4

1 回答 1

1

这个答案将试图让你意识到出了什么问题。

很明显，mergeSort 不会对一个元素数组做任何事情，但是如果有两个（例如 [2,1]）会发生什么？您提到结果列表（列表 A）中的元素比以前更多。为什么？对那个列表做了什么合并？提示。

于 2013-04-18T03:00:38.220 回答