Java MergeSort – 内存不足错误：Java堆空间

我正在尝试使用Java进行排序。

我现在正在进行合并排序… Eclipse正在输出Out Of Memory Error: Java Heap space ，但我不知道如何调试它。

我觉得我的代码还可以 – 有什么想法吗？

 import java.util.ArrayList; import java.util.List; public class Sorts { List initialList; public Sorts() { initialList = new ArrayList(); 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 splitList(List splitMe) { List left = new ArrayList(); List right = new ArrayList(); 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 mergeThem(List left, List right) { List sortedList = new ArrayList(); 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 mergeThem(List left, List right) { //set the sorted list List sortedList = new ArrayList(); //getting the iterators for both lists because List#get(x) can be O(N) on LinkedList Iterator itLeft = left.iterator(); Iterator 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; } 

Answer 2

 while (left.size() > 0 || right.size() > 0) { 

因为您没有从左侧或右侧删除任何项目而不退出，因此您不断向sortedList添加项目，直到内存不足为止。 您检查它们中的任何一个是否大于0但是您永远不会删除任何项目，因此检查将永远不会返回false，即无限循环。