Java MergeSort - 内存不足错误 : Java Heap Space

Question

我正在尝试用 Java 进行一些排序练习。

我现在正在处理合并排序... Eclipse 正在输出 内存不足错误:Java 堆空间，但我不知道如何调试它。

我觉得我的代码没问题 - 有什么想法吗？

import java.util.ArrayList;
import java.util.List;
public class Sorts {
    List<Integer> initialList;

    public Sorts() {
        initialList = new ArrayList<Integer>();
        initialList.add(2);
        initialList.add(5);
        initialList.add(9);
        initialList.add(3);
        initialList.add(6);

        System.out.print("List: [");
        for (int values : initialList) {
            System.out.print(values);
        }
        System.out.println("]");

        splitList(initialList);
    }

    public List<Integer> splitList(List<Integer> splitMe)   {
        List<Integer> left = new ArrayList<Integer>();
        List<Integer> right = new ArrayList<Integer>();

        if (splitMe.size() <= 1) {
            return splitMe;
        }

        int middle = splitMe.size()/2;
        int i = 0;
        for (int x: splitMe) {
            if (i < middle) {
                left.add(x);
            }
            else {
                right.add(x);
            }
            i++;
        }
        left = splitList(left);
        right = splitList(right);

        return mergeThem(left, right);
    }

    public List<Integer> mergeThem(List<Integer> left, List<Integer> right) {
        List<Integer> sortedList = new ArrayList<Integer>();
        int x = 0;
        while (left.size() > 0 || right.size() > 0) {
            if (left.size() > 0 && right.size() > 0) {
                if (left.get(x) > right.get(x)) 
                    sortedList.add(left.get(x));
                else 
                    sortedList.add(right.get(x));
            }
            else if (left.size() > 0) {
                sortedList.add(left.get(x));
            }
            else if (right.size() > 0) {
                sortedList.add(right.get(x));
            }
        }
        return sortedList;
    }   
}

Answer 1

使用 Java 元素提供 mergeThem 方法的可能实现:

public List<Integer> mergeThem(List<Integer> left, List<Integer> right) {
    //set the sorted list
    List<Integer> sortedList = new ArrayList<Integer>();
    //getting the iterators for both lists because List#get(x) can be O(N) on LinkedList
    Iterator<Integer> itLeft = left.iterator();
    Iterator<Integer> itRight = right.iterator();
    //getting flags in order to understand if the iterator moved
    boolean leftChange = true, rightChange = true;
    //getting the current element in each list
    Integer leftElement = null, rightElement = null;
    //while there are elements in both lists
    //this while loop will stop when one of the list will be fully read
    //so the elements in the other list (let's call it X) must be inserted
    while (itLeft.hasNext() && itRight.hasNext()) {
        //if left list element was added to sortedList, its iterator must advance one step
        if (leftChange) {
            leftElement = itLeft.next();
        }
        //if right list element was added to sortedList, its iterator must advance one step
        if (rightChange) {
            rightElement = itRight.next();
        }
        //cleaning the change flags
        leftChange = false;
        rightChange = false;
        //doing the comparison in order to know which element will be inserted in sortedList
        if (leftElement <= rightElement) {
            //if leftElement is added, activate its flag
            leftChange = true;
            sortedList.add(leftElement);
        } else {
            rightChange = true;
            sortedList.add(rightElement);
        }
    }
    //this is the hardest part to understand of this implementation
    //java.util.Iterator#next gives the current element and advance the iterator on one step
    //if you do itLeft.next then you lost an element of the list, that's why we have leftElement to keep the track of the current element of left list (similar for right list)
    if (leftChange && rightElement != null) {
        sortedList.add(rightElement);
    }
    if (rightChange && leftElement != null) {
        sortedList.add(leftElement);
    }
    //in the end, you should add the elements of the X list (see last while comments).
    while (itLeft.hasNext()) {
        sortedList.add(itLeft.next());
    }
    while (itRight.hasNext()) {
        sortedList.add(itRight.next());
    }
    return sortedList;
}