快速排序大型阵列的stackoverflow错误

Question

所以我被分配实现快速排序算法并比较大小为500,3500和80000的数组的运行时间.数组填充了随机数:

(INT)的Math.random()*1000000

我的快速排序算法适用于大小为500和3500的数组,但是当我尝试对大小为80000的第三个数组进行排序时,我总是遇到堆栈溢出错误.我的其他排序算法处理这些数组就好了.

我的快速排序方法:

public static void quickSort(int[] a, int p, int r)
{
    if(p<r)
    {
        int q=partition(a,p,r);
        quickSort(a,p,q);
        quickSort(a,q+1,r);
    }
}

我的分区方法:

private static int partition(int[] a, int p, int r) {

    int x = a[p];
    int i = p;
    int j = r;

    while (true) {
        do {
            i++;
        } while (i < r && a[i] < x);
        do {
            j--;
        } while (j > p && a[j] > x);

        if (i < j) {
            int tmp = a[i];
            a[i++] = a[j];
            a[j--] = tmp;
        } else {
            return j;
        }
    }
}

我读到我可以简单地在VM选项中更改我的堆栈大小(不知道该怎么做),但这只是忽略了算法中的问题.是什么导致错误？谢谢!

编辑:这是我的驱动程序类:

public class Driver {

public static void main(String[] args) {

    int[] array1 = new int[500];
    int[] array2 = new int[3500];
    int[] array3 = new int[80000];

    for(int i=0; i<array1.length; i++) {
        array1[i]=(int)(Math.random()*100000);
    }

    for(int i=0; i<array2.length; i++) {
        array2[i]=(int)(Math.random()*100000);
    }

    for(int i=0; i<array3.length; i++) {
        array3[i]=(int)(Math.random()*100000);
    }

    //~~~~~~~~~~~INSERTION~~~~~~~~~~~~~~~//

    System.out.println("INSERTION SORT:\n_______________");
    System.out.println("500 Elements: "+SortTimes.runTime(SortTimes.INSERTION,array1)+" ms");
    System.out.println("3500 Elements: "+SortTimes.runTime(SortTimes.INSERTION,array2)+" ms");
    System.out.println("80000 Elements: "+SortTimes.runTime(SortTimes.INSERTION,array3)+" ms");

    //~~~~~~~~~~~BUBBLE~~~~~~~~~~~~~~~//

    System.out.println("\n\nBUBBLE SORT:\n_______________");
    System.out.println("500 Elements: "+SortTimes.runTime(SortTimes.BUBBLE,array1)+" ms");
    System.out.println("3500 Elements: "+SortTimes.runTime(SortTimes.BUBBLE,array2)+" ms");
    System.out.println("80000 Elements: "+SortTimes.runTime(SortTimes.BUBBLE,array3)+" ms");

    //~~~~~~~~~~~MERGE~~~~~~~~~~~~~~~//

    System.out.println("\n\nMERGE SORT:\n_______________");
    System.out.println("500 Elements: "+SortTimes.runTime(SortTimes.MERGE,array1)+" ms");
    System.out.println("3500 Elements: "+SortTimes.runTime(SortTimes.MERGE,array2)+" ms");
    System.out.println("80000 Elements: "+SortTimes.runTime(SortTimes.MERGE,array3)+" ms");

    //~~~~~~~~~~~QUICK~~~~~~~~~~~~~~~//

    System.out.println("\n\nQUICK SORT:\n_______________");
    System.out.println("500 Elements: "+SortTimes.runTime(SortTimes.QUICK,array1)+" ms");
    System.out.println("3500 Elements: "+SortTimes.runTime(SortTimes.QUICK,array2)+" ms");
    System.out.println("80000 Elements: "+SortTimes.runTime(SortTimes.QUICK,array3)+" ms");
}

}

这是我的SortTimes类:

public class SortTimes {

public final static int MERGE = 1;
public final static int QUICK = 2;
public final static int BUBBLE = 3;
public final static int INSERTION = 4;

public static double runTime(int sortMethod, int[] array) {

    double startTime;
    double endTime;

    switch(sortMethod) {
        case MERGE:
            startTime = System.currentTimeMillis();
            lab12.mergeSort(array);
            endTime = System.currentTimeMillis();
            break;

        case QUICK:
            startTime = System.currentTimeMillis();
            lab12.quickSort(array, 0, array.length-1);
            endTime = System.currentTimeMillis();
            break;

        case BUBBLE:
            startTime = System.currentTimeMillis();
            lab12.bubbleSort(array);
            endTime = System.currentTimeMillis();
            break;

        case INSERTION:
            startTime = System.currentTimeMillis();
            lab12.insertionSort(array);
            endTime = System.currentTimeMillis();
            break;

        default:
            startTime = -1;
            endTime = 0;
            break;
    }

    return endTime-startTime;
}

}

Answer 1

这是您的快速排序：

public static void quickSort(int[] a, int p, int r)
{
    if(p<r)
    {
        int q=partition(a,p,r);
        quickSort(a,p,q);
        quickSort(a,q+1,r);
    }
}

它可以工作，但在最坏的情况下它使用 O(rp) 堆栈空间。对于真正的实现来说这太多了。不过，解决方法很简单——在较小的分区上递归，然后在较大的分区上循环。在较小的分区上递归意味着无论如何只使用 O(log(rp)) 堆栈空间：

public static void quickSort(int[] a, int p, int r)
{
    while(p<r)
    {
        int q=partition(a,p,r);
        if (q-p <= r-(q+1))
        {
            quickSort(a,p,q);
            p=q+1;
        }
        else
        {
            quickSort(a,q+1,r);
            r=q;
        }
    }
}

编辑：所以，这就是真正的快速排序实现确保在最坏情况下没有堆栈溢出的方式......

但当你用随机数初始化数组时，最坏的情况永远不会发生。

你说你用 初始化了数组(int)Math.random()*1000000。检查优先级表！转换发生在乘法之前，因此它始终为 0，这就是为什么您会得到最坏情况的行为。你要(int)(Math.random()*1000000)。

编辑：你的分区功能也被破坏了。它总是将 a[p] 保留在位置 p 处，即使它是数组中最大的元素

Answer 2

如果quickSort()仍然使用pivot x = a[p]，而不是x = a[(p+r)/2]，那么如果数据已经排序，quickSort()可能会出现堆栈溢出。您是否有可能对已按先前排序排序的数据运行 fastSort() ？