0

已解决：我在每次递归调用时都实例化一个新的 Random 对象。我把它作为一个静态变量放在 Quicksort 之外，现在它工作得很好。

我正在用 Java 编写 Quicksort 以完成学校作业，但我被卡住了。我正在使用类中的nextInt()方法随机选择枢轴Random。这意味着我正在调用nextInt()每个递归步骤。我的快速排序在具有 20000 个元素的数组中完美地完成了这项工作。但是当我尝试对包含 40000 个元素的数组进行排序时，会StackOverflowError出现这种情况

   java.lang.StackOverflowError: null (in java.util.Random)

我已经在谷歌上搜索了这个错误，但对我没有任何帮助。我的猜测是我用完了随机整数，但我在 java 中太菜鸟了，我什至不买我自己的猜测。

这是我的代码（西班牙语是我的第一语言，对于蹩脚的英语和西班牙语代码感到抱歉）

public static void quicksort(String[] A, int min, int max){// llamar ord(A, 0, n-1);
    if(min >= max){
        return;
    }
    Random rand = new Random(); 
    int pivote = particionar(A, min, max, rand);
    quicksort(A, min, pivote-1);
    quicksort(A, pivote + 1, max);
    }

public static int particionar(String[] A, int min, int max, Random rand){    
    int menores = min + 1;
    int mayores = max;

    int pivote = rand.nextInt(max-min+1) + min;
    String pivotstr = A[pivote];
    //dejar pivote al principio
    String aux = A[min];
    A[min] = A[pivote];
    A[pivote] = aux;

    while(menores <= mayores){
        if(A[menores].compareTo(pivotstr) <= 0){
            menores++;
        }
        else{//intercambiar
            String aux2 = A[menores];
            A[menores] = A[mayores];
            A[mayores] = aux2;
            mayores--;
        }
    }
    //mover pivote donde corresponde
    String aux3 = A[min];
    A[min] = A[mayores];
    A[mayores] = aux3;

    return mayores;

}
4

2 回答 2

0

StackOverflowError 是当你的递归运行太深时你得到的。

解决方案：将其转换为迭代版本。 从递归到迭代的方法

于 2013-06-14T06:47:12.203 回答
0

您的程序正在生成太多级别的递归调用，并且堆栈上的内存不足。一种解决方案是在运行时增加堆栈大小，如此处所述。另一种是按照 lorenzo.marcon 的建议从递归转换为迭代。

Java 的默认随机数生成器是一个具有 48 位种子大小的线性同余生成器，因此它的循环长度应该是 2**48 量级。这意味着您不会用完随机整数，而是在那么多值之后重复序列。

堆栈溢出问题的一个重要原因是您在每次递归调用时都会实例化一个新的 Random 对象。你不会每次想喝水就挖一口新井，大多数人会挖一口井，然后再重新打水。同样，推荐的做法是实例化一个静态 Random 对象并重新访问它以获得更多值，除非您真的知道自己在做什么 - 您几乎从不需要多个 Random 对象。

于 2013-06-14T13:55:46.670 回答