java - 具有许多元素的快速排序会导致 StackOverflowError

Question

美好的一天!运行快速排序算法时，我收到 StackOverflowError 错误。当数组中的元素 > 50 000 时，会发生此错误。

我的代码如下:

public void recQuickSort(int left, int right)
{
    if(right-left <= 0)
        return;
    else {
        long pivot = a[right];
        int partition = partitionIt(left, right, pivot);
        recQuickSort(left, partition-1);  
        recQuickSort(partition+1, right); 
    }
}
public int partitionIt(int left, int right, long pivot) {
    int leftPtr = left - 1;
    int rightPtr = right;
    while (true) {
        while (a[++leftPtr] < pivot) ;
        while (rightPtr > 0 && a[--rightPtr] > pivot) ;
        if (leftPtr >= rightPtr)
            break;
        else
            swap1(leftPtr, rightPtr);
    }
        swap1(leftPtr, right);
        return leftPtr;
}

public void swap1(int dex1, int dex2)  // Permutation of two elements
{
    long temp;
    temp = a[dex1];
    a[dex1] = a[dex2];
    a[dex2] = temp;
}

当元素 > 50 000 时如何修复此错误？

Answer 1

仅在较小的分区上递归，然后更新左侧或右侧并循环返回较大的分区。这将防止堆栈溢出(限制为 log2(n) 堆栈帧)，但不会防止最坏情况的时间复杂度 O(n^2)。

public void recQuickSort(int left, int right)
{
    while(true){
        if(right-left <= 0)
            return;
        else {
            long pivot = a[right];
            int partition = partitionIt(left, right, pivot);
            if((partition - left) <= (right - partition)){
                recQuickSort(left, partition-1);
                left = partition+1;
            } else {
                recQuickSort(partition+1, right);
                right = partition-1;
            }
        }
    }
}