具有许多元素的 QuickSort 导致 StackOverflowError [英] QuickSort with Many Elements causes StackOverflowError

问题描述

美好的一天！运行quickSort 算法时出现StackOverflowError.当数组中的元素 > 50 000 时会发生此错误.

Good day! I am getting a StackOverflowError when running my quickSort algorithm. This error occurs when elements in the array > 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 时如何修复此错误?

How can I fix this error when elements > 50 000?

推荐答案

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

Only recurse on the smaller partition, then update left or right and loop back for the larger partition. This will prevent stack overflow (limit to log2(n) stack frames), but won't prevent worst case time complexity 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;
            }
        }
    }
}

这篇关于具有许多元素的 QuickSort 导致 StackOverflowError的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！