0

我有作业 - 在 java 中编写一个合并排序算法。我使用 LinkedList 来存储我的数据。我尝试将伪代码从维基百科（http://en.wikipedia.org/wiki/Merge_sort）转换为 java，但它不起作用。我不知道为什么，我需要你们的帮助。

这是我的 MergeSort 类。

import java.util.Comparator;

public class MergeSort {
private final Comparator comparator;

public MergeSort(Comparator comparator) {
    this.comparator = comparator;
}

public LinkedList sort(LinkedList list) {
    if(list.size() <= 1) {
        return list;
    }

    LinkedList left = new LinkedList();
    LinkedList right = new LinkedList();

    int middle = list.size() / 2;
    for(int i = 0; i < middle; i++) {
        left.add(list.get(i));
    }

    for(int i = list.size(); i >= middle; i--) {
        right.add(list.get(i));
    }

    left = sort(left);
    right = sort(right);

    return merge(left, right);
}

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

    while(left.size() > 0 || right.size() > 0) {
        if(left.size() > 0 && right.size() > 0) {
            if(comparator.compare(left.get(0), right.get(0)) <= 0) {
                result.add(left.delete(0));
            }
            else {
                result.add(right.delete(0));
            }
        }
        else if(left.size() > 0) {
            result.add(left.delete(0));
        }
        else if(right.size() > 0) {
            result.add(right.delete(0));
        }
    }
    return result;
}

}

其中有一个“StackOverflowError 异常”。我试图删除错误，但我不能。谢谢你的帮助。

PS对不起我糟糕的语言。:(

4

1 回答 1

0

在第 33 行，您的上数组索引需要从列表大小减一开始：

        for(int i = list.size()-1; i >= middle; i--) {
于 2013-04-24T18:07:40.857 回答