0

我编写的这段代码在达到一定的输入大小之前效果很好。如果输入太大，我会得到“java.lang.StackOverflowError”。我已经阅读了有关此主题的 stackoverflow 上的其他一些条目，并且我认为我的递归出现错误 - 但我找不到它。这是代码：

public int partition(int[] A, int l, int r, int x){

    int i = l-1;
    int j = r;
    int exchange;

    while(i <= j){
        while(A[i] > x){
            i++;
        }

        while(j >= i && A[j] <= x){
            j--;
        }

        if(i < j){
            exchange = A[i];
            A[i] = A[j];
            A[j] = exchange;
        }
    }

    if(A[i] < A[r]){
        exchange = A[i];
        A[i] = A[r];
        A[r] = exchange;
    }

    return i;
}

public void quicksort(int[] A, int l, int r){
    int pivot = 0;
    int x = 0;

    if(l < r){
        x = A[r];
        pivot = partition(A, l, r, x);
        quicksort(A, l, pivot-1);
        quicksort(A, pivot+1, r);
    }
}
4

1 回答 1

1

如果输入变得太大

“太大”到底是什么意思？每个足够深的递归都可能导致堆栈溢出，因为堆栈用于将递归方法的所有局部变量保留在所有递归级别上。

这是递归的内在缺点，也是迭代实现通常优于递归的原因。

于 2013-05-11T16:00:42.530 回答