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

Question

我想在Java中进行一些排序练习。

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

我觉得我的代码是好的 - 任何想法？

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; 
} 

Answer 2

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

不会退出，因为你不从你的左边或右边删除任何项目，就不断增加项目排序列表，直到内存用完。你检查它们中的任何一个是否大于0，但是你永远不会删除任何项目，所以检查将永远不会返回假，也就是无限循环。