Java QuickSort 堆栈溢出 20,000 或更多整数

Question

当我对包含 20,000 个或更多整数的数组运行快速排序时，出现以下错误。

线程“main”中出现异常 java.lang.StackOverflowError 在project1.Project1.quickSort(Project1.java:31)

我使用 p=0 和 r=array.length-1 调用 QuickSort

public static int[] createArray(int size)
{
    int []array = new int[size];
    for(int i=0;i<size;i++)
    {
        array[i]= randomGenerator.nextInt(100000);
    }
    return array;
}
public static void quickSort(int p, int r)
{
    if(p < r)
    {
        int q = partition(p, r);
        quickSort(p,q - 1);
        quickSort(q+1,r);
    }
}

public static int partition(int p,int r)
{
    int x = array[r];
    int i = p-1;
    for(int j=p;j<=r-1;j++)
    {
        if(array[j]<= x)
        {
            i++;
            swap(i,j);
        }
    }
    swap(i+1,r);
    return i+1;
}

public static void swap(int i, int j)
{
    int temp = array[i];
    array[i]= array[j];
    array[j]= temp;
}

public static void main(String[] args) 
{
    //Get all the required input data
    System.out.print("Size to be tested: ");
    sc = new Scanner(System.in);
    int input = sc.nextInt();
    float selectionAvg= 0,quickAvg= 0,countAvg=0, medianAvg=0;

    //Run the Quick sort algorithm
    array= startArray;
    int low= 0;
    int high = array.length-1;
    startTime= System.currentTimeMillis();
    quickSort(low, high);
    endTime = System.currentTimeMillis();
    time= endTime - startTime;
    System.out.println("Quick Sort Time: " + time + " milliseconds");  
    //printArray();
    quickAvg+= time;
}

Answer 1

您可能会考虑修改您的程序以进行迭代。这样做的基本思想是使用自己的堆栈来处理当前由递归处理的作业。

阅读此内容 article以供进一步引用。