java - 大型数组的快速排序 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(r-p) 堆栈空间。这对于实际实现来说太多了。不过，解决方法很简单——您在较小 分区上递归，然后循环查找较大的分区。在较小的分区上递归意味着无论如何您都只使用 O(log(r-p)) 堆栈空间:

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，即使它是数组中最大的元素