具有多个元素的QuickSort导致StackOverflowError

Question

美好的一天！运行我的quickSort算法时，我得到了一个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;
            }
        }
    }
}