java - Java中的递归合并排序

Question

首先，在此先感谢所有回复，非常感谢他们。现在到这篇文章的目的；我在 Java 中实现合并排序时遇到问题。我得到一个空指针异常，但是，我无法弄清楚错误是什么，对我来说代码看起来不错。到目前为止，这是我所拥有的：

public List mSort(List l) {

    if (l.size() <= 1)
        return l;

    List left = null;
    List right = null;
    int mid = l.size() / 2;


    for (int x = 0; x < mid; x++)
        left.add(l.get(x));
    for (int x = 0; x >= mid; x++)
        right.add(l.get(x));

    left = mSort(left);
    right = mSort(right);

    return merge(left, right);
}

public List merge(List left, List right) {

    List r = null;
    while (left.size() > 0 || right.size() > 0) {
        if (left.size() > 0 && right.size() > 0)
            if (left.get(0) <= right.get(0)) {
                r.add(left.get(0));
                left.remove(0);
            }
            else {
                r.add(right.get(0));
                right.remove(0);
            }
        else if (left.size() > 0) {
            r.add(left.get(0));
            left.remove(0);

        }
        else if (right.size() > 0) {
            r.add(right.get(0));
            right.remove(0);
        }
    }
    return r;


}

...显然，指针异常来自“mSort”方法中的“For”语句，任何可以指出我的错误或指导我正确方向的东西都非常感谢！！！

Answer 1

left并且right是空的，你不能添加它！！！

List left = new ArrayList();
List right = new ArrayList();

Answer 2

for (int x = 0; x < mid; x++)
        left.add(l.get(x));
    for (int x = 0; x >= mid; x++)
        right.add(l.get(x));

一定是

int x = 0;
for (; x < mid; x++)
    left.add(l.get(x));
for (; x < l.size(); x++)
    right.add(l.get(x));