MergeSort 算法 - java

Question

我在 Java 中执行 MergeSort 时遇到问题。我的代码看起来像这样，我不知道我在哪里犯了错误。

public List sort(List list) {
        return mergesort(list, 0, list.size() - 1);
    }

    private List mergesort(List list, int startIndex, int endIndex) {
        if (startIndex == endIndex) {
            List temp = new ArrayList();
            temp.add(list.get(0));
            return temp;
        }
        int splitIndex = ((startIndex + endIndex) / 2);
        List list1 = mergesort(list, startIndex, splitIndex);
        List list2 = mergesort(list, (splitIndex + 1), endIndex);
        return merge(list1, list2);
    }

    private List merge(List left, List right) {
        List result = new ArrayList();
        ListIterator l = new ListIterator(left);
        ListIterator r = new ListIterator(right);
        l.first();
        r.first();
        while (!l.isDone() && !r.isDone()) {
            if (comparator.compare(l.current(), r.current()) <= 0) {
                result.add(l.current());
                l.next();
            } else {
                result.add(r.current());
                r.next();
            }
        }
        while (!l.isDone()) {
            result.add(l.current());
            l.next();
        }
        while (!r.isDone()) {
            result.add(r.current());
            r.next();
        }
        return result;

    }

为了测试我的算法，我使用了人员列表并按年龄升序对他们进行排序：

0. Jan, Kowalski, 60
1. Jerzy, Adamczewski, 59
2. Jan, Kowalski, 48
3. Adam, Malysz, 40
4. Bartosz, Tusk, 50
5. Zygmunt, Jacewicz, 41

输出如下所示：

0. Adam, Malysz, 40
1. Adam, Malysz, 40
2. Adam, Malysz, 40
3. Adam, Malysz, 40
4. Adam, Malysz, 40
5. Adam, Malysz, 40

Answer 1

这个方块看起来不对。

if (startIndex == endIndex) {
    List temp = new ArrayList();
    temp.add(list.get(0));
    return temp;
}

也许，你的意思是 temp.add(list.get(startIndex)); ?

Answer 2

您的合并函数似乎总是采用相同的最小元素，直到列表为空。这给我的印象是您对 "ListIterator::current()" 和 "ListIterator::next()".

的使用存在问题

我对ListIterators不是很熟练，所以我的建议是直接对list进行操作。这也简化了在其中一个列表用完元素后添加两个列表的剩余元素：

private List merge(List left, List right) {
    List result = new LinkedList();

    while (!left.isEmpty() && !right.isEmpty()) {
        if (comparator.compare(left.get(0), right.get(0)) <= 0) {
            result.add(left.remove(0));
        } else {
            result.add(right.remove(0));
        }
    }

    // add what is left in the lists
    result.addAll(left);
    result.addAll(right);

    return result;
}

PS：我的IDE中没有检查这段代码，所以谨慎使用。理想情况下，您应该准备好测试来检查您的代码 - TDD 是每个软件开发人员都应该遵循的非常好的方法:)

MergeSort 算法 - java

MergeSort algorithm - java

java

sorting

algorithm

mergesort