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，但是你永遠不會刪除任何項目，所以檢查將永遠不會返回假，也就是無限循環。