Java中的堆栈问题

Question

我在java中使用堆栈时遇到了一些问题...我使用ArrayList实现快速排序 - 我将在最后附上我的完整代码，但以下是相关的部分（请牢记我已经调试了几个小时，完全不知道出了什么问题，所以如果你看到事情以奇怪的方式完成，那很可能是因为我试图检查那里的错误）：

那显然是正在执行的调用次数过多：

  QuickSort(numArray, m+1, right); 

在这里失败：

//Swap pivot and left 
     numArray.set(pivot, leftVal); 

我得到的输出：

Starting sort number: [1] : RandomPivot [ON] : Sorting [RANDOM] 
Sorted: 2496 elements. 
Took: 53 milliseconds. 

Starting sort number: [2] : RandomPivot [ON] : Sorting [RANDOM] 
Sorted: 4988 elements. 
Took: 25 milliseconds. 

Starting sort number: [3] : RandomPivot [ON] : Sorting [RANDOM] 
Sorted: 7478 elements. 
Took: 49 milliseconds. 

Starting sort number: [4] : RandomPivot [ON] : Sorting [RANDOM] 
Sorted: 9953 elements. 
Took: 85 milliseconds. 

Starting sort number: [5] : RandomPivot [ON] : Sorting [RANDOM] 
Sorted: 12416 elements. 
Took: 131 milliseconds. 

Starting sort number: [1] : RandomPivot [ON] : Sorting [SORTED] 
Sorted: 2497 elements. 
Took: 1 milliseconds. 

Starting sort number: [2] : RandomPivot [ON] : Sorting [SORTED] 
Sorted: 4984 elements. 
Took: 1 milliseconds. 

Starting sort number: [3] : RandomPivot [ON] : Sorting [SORTED] 
Sorted: 7482 elements. 
Took: 2 milliseconds. 

Starting sort number: [4] : RandomPivot [ON] : Sorting [SORTED] 
Sorted: 9950 elements. 
Took: 2 milliseconds. 

Starting sort number: [5] : RandomPivot [ON] : Sorting [SORTED] 
Sorted: 12424 elements. 
Took: 2 milliseconds. 

Starting sort number: [1] : RandomPivot [ON] : Sorting [REVERSE SORTED] 
Sorted: 2494 elements. 
Took: 2 milliseconds. 

Starting sort number: [2] : RandomPivot [ON] : Sorting [REVERSE SORTED] 
Sorted: 4988 elements. 
Took: 10 milliseconds. 

Starting sort number: [3] : RandomPivot [ON] : Sorting [REVERSE SORTED] 
Sorted: 7470 elements. 
Took: 35 milliseconds. 

Starting sort number: [4] : RandomPivot [ON] : Sorting [REVERSE SORTED] 
Sorted: 9962 elements. 
Took: 50 milliseconds. 

Starting sort number: [5] : RandomPivot [ON] : Sorting [REVERSE SORTED] 
Sorted: 12419 elements. 
Took: 65 milliseconds. 

Starting sort number: [1] : RandomPivot [OFF] : Sorting [RANDOM] 
Sorted: 2497 elements. 
Took: 5 milliseconds. 

Starting sort number: [2] : RandomPivot [OFF] : Sorting [RANDOM] 
Sorted: 4984 elements. 
Took: 54 milliseconds. 

Starting sort number: [3] : RandomPivot [OFF] : Sorting [RANDOM] 
Sorted: 7473 elements. 
Took: 47 milliseconds. 

Starting sort number: [4] : RandomPivot [OFF] : Sorting [RANDOM] 
Sorted: 9958 elements. 
Took: 80 milliseconds. 

Starting sort number: [5] : RandomPivot [OFF] : Sorting [RANDOM] 
Sorted: 12419 elements. 
Took: 130 milliseconds. 

Starting sort number: [1] : RandomPivot [OFF] : Sorting [SORTED] 
Sorted: 2498 elements. 
Took: 11 milliseconds. 

Starting sort number: [2] : RandomPivot [OFF] : Sorting [SORTED] 
Sorted: 4991 elements. 
Took: 44 milliseconds. 

Starting sort number: [3] : RandomPivot [OFF] : Sorting [SORTED] 
Sorted: 7474 elements. 
Took: 97 milliseconds. 

Starting sort number: [4] : RandomPivot [OFF] : Sorting [SORTED] 
Exception in thread "main" java.lang.StackOverflowError 
at java.util.ArrayList.set(Unknown Source) 
at Sorter.QuickSort(Sorter.java:64) 
at Sorter.QuickSort(Sorter.java:107) 
at Sorter.QuickSort(Sorter.java:107) 
at Sorter.QuickSort(Sorter.java:107) 
at Sorter.QuickSort(Sorter.java:107) 
    (on and on and on and on) 

测试，一旦我得到过去〜7500作为我的ArrayList的大小，它总是失败。总是在“ArrayList.set（）”失败，我对此毫无头绪。正如你所看到的那样 - 所有其他的排序类型都可以在这个数量上正常工作，但是对于排序列表，我必须n次调用“m + 1，right”，其中n是列表的大小。

我已经试过这样：

if(m-1>left && m-1<right) 
     QuickSort(numArray, left, m-1); 
    if(m+1<right && m+1>left) 
     QuickSort(numArray, m+1, right); 

，但我得到了同样的错误无论哪种方式，我想它更容易，如果它离开了理解。

如果我可以增加堆栈大小，不知何故，我可能会推迟错误，这将允许我至少分析不同的方法。

我通过eclipse运行这段代码，如果这有什么区别。谢谢！ （现在的完整代码）

import java.util.ArrayList; 
import java.util.HashSet; 
import java.util.Random; 
import java.util.Set; 
import java.util.TreeSet; 


public class Sorter { 

//STATE: 
public boolean test=false; 
public boolean randomPivot=false; 
Random r = new Random(); 
public int sortMethod=1; 

public static int RANDOM=1; 
public static int SORTED=2; 
public static int REVERSE_SORTED=3; 


public Sorter(){ } 


public ArrayList<Integer> SlowSort(ArrayList<Integer> numArray){ 

    //Add "infinity" to the end 
    numArray.add(Integer.MAX_VALUE); 


    //TIME AND RUN QUICKSORT 
    long startTime = System.currentTimeMillis(); 
    numArray=QuickSort(numArray, 0, numArray.size()-2); 
    long stopTime = System.currentTimeMillis(); 
    long runTime = stopTime - startTime; 

    //Remove "infinity" from the end 
    numArray.remove(numArray.size()-1); 

    //TODO: Printing effs it up? idk 
    //  printArrayWithMessage("Sort Finished.", numArray); 

    //PRINT COMPLETION MESSAGE AND RETURN 
    System.out.println("Sorted: "+numArray.size()+" elements.\nTook: " + runTime+" milliseconds.\n"); 
    return numArray; 
} 


public ArrayList<Integer> QuickSort(ArrayList<Integer> numArray, int left, int right){ 
    if(left>=right){ 
     return numArray; 
    } 

    //Correctly Initialize Pivot 
    int pivot=0; 
    if(randomPivot){ 
     pivot = r.nextInt(right-left); 
    } 
    pivot+=left; 

    //Swap pivot and left 
    Integer temp = numArray.get(pivot); 
//  System.out.println(numArray.size()+" "+pivot); 
    int leftVal=numArray.get(left); 
    numArray.set(pivot, leftVal); 
    pivot=temp; 
    numArray.set(left, pivot); 

    Integer m=0; 

    //REPEAT: 
    while(true){ 
     int i=left+1; 
     int j=right+1; 

     while(numArray.get(i).intValue()<pivot){ 
      i++; 
     } 
     while(numArray.get(j).intValue()>pivot){ 
      j--; 
     } 

     if(i<j){ 
      //Swap i and j 
      if(test) printArrayWithMessage("[SWAP] (i="+i+") and (j="+j+")", numArray); 

      Integer a=numArray.get(i); 
      numArray.set(i, numArray.get(j)); 
      numArray.set(j, a); 
     } 

     if(i>j){ 
      //Swap pivot and j 
      if(test) printArrayWithMessage("[SWAP] (j="+j+") and (pivot="+left+")", numArray); 

      numArray.set(left, numArray.get(j)); 
      numArray.set(j, pivot); 
      m=j; 

      break; 
     } 
    } 

    if(test) printArrayWithMessage("Iteration Finished... Left: "+left+" Right: "+right, numArray); 


     QuickSort(numArray, left, m-1); 
     QuickSort(numArray, m+1, right); 

    return numArray; 
} 

public void benchmark(){ 

    for(int i=1;i<6;i++){ 
     //CREATE BLANK DATA STRUCTURES 
     ArrayList<Integer> numList = new ArrayList<Integer>(); 
     Set<Integer> doublesFilter; 

     if(sortMethod==RANDOM){ 
      doublesFilter = new HashSet<Integer>(); 
     }else{ 
      doublesFilter = new TreeSet<Integer>(); 
     } 
     //FILL ARRAYLIST WITH UNIQUE NUMBERS 
     for(int j=0;j<2500*i;j++){ 
      int num=r.nextInt(1000000); 
      if(doublesFilter.add(num)){ 
       if(sortMethod==RANDOM){ 
        numList.add(num); 
       } 
      } 
     } 
     if(sortMethod==SORTED){ 
      numList.add(0); 
      numList.ensureCapacity(doublesFilter.size()); 
      numList.addAll(doublesFilter); 
      numList.remove(0); 
     } 
     else if(sortMethod==REVERSE_SORTED){ 
      numList.add(0); 
      numList.ensureCapacity(doublesFilter.size()); 
      numList.addAll(((TreeSet<Integer>) doublesFilter).descendingSet()); 
      numList.remove(0); 
     } 


     System.out.println("Starting sort number: ["+i+"] : "+getMode()); 
     numList=SlowSort(numList); 
    } 
} 


public void printArrayWithMessage(String s, ArrayList<Integer> list){ 
    System.out.println(s); 
    System.out.println(list); 
    System.out.println(); 
} 

public String getMode(){ 

    String rPivot="OFF"; 
    if(randomPivot) rPivot="ON"; 


    String sortMode="UNDEFINED"; 
    if(sortMethod==1)sortMode="RANDOM"; 
    if(sortMethod==2)sortMode="SORTED"; 
    if(sortMethod==3)sortMode="REVERSE SORTED"; 

    return "RandomPivot ["+rPivot+"] : "+"Sorting ["+sortMode+"]"; 
} 

} 

Answer 1

如你所指出的，具有快速排序时提供一个排序后的数组，并最终使O（n）的递归调用，因为分区仅删除在每个细分步骤一种元素最坏的情况下的性能。在数组未被排序的其他情况下，分区更加有效，因此您最终会收到O（lgN）递归调用。 O（n）递归调用超过O（lgN）调用不会的最大堆栈帧数。

编辑（附加说明）： 在快速排序中使用随机数据透视的好处和意图之一是确保分区/子问题的大小是O（n）而不是O（1）在最坏的情况下的行为后一种情况（没有随机数据库+排序输入）就是你看到堆栈溢出错误的地方。

Answer 2

递归实现总是会在“正确”情况下（即大数据集）产生一个stackoverflow。另外，看看一些回答类似的问题：

Got stackoverflowerror when using quickSort, can I increase the stack and the heap?

Some issues in implementing QuickSort in java