大型数组的快速排序 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 选项中更改我的堆栈大小（不知道该怎么做），但这只是忽略了我的算法中的问题。是什么导致了错误？谢谢！

我的driverclass:

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 class:

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 class quickSortTest {
public static void main(String[] args) {
    int max = 800000;
    int[] array = new int[max];
    for (int i = 0; i < max; ++i) {
        array[i] = (int) Math.random() * 1000000;
    }
    long start = System.currentTimeMillis();
    quickSort(array, 0, max - 1);
    System.out.println("time:"+(System.currentTimeMillis()-start));
    System.out.println(testSortResult(array));
}

public static boolean testSortResult(int[] array){
    for(int i=1;i<array.length;++i){
        if(array[i]<array[i-1]){
            return false;
        }
    }
    return true;
}

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;
        }
    }
}
}

我测试了你的代码，即使数组长度为 800000 也没有问题。

Answer 2

由于此程序是递归的，并且 java 在有点深的递归中内存效率不高，请尝试通过 IDE 增加为您的程序分配的内存量。

由于您使用的是 Intellij，请尝试如下增加内存。

更多信息：https://www.jetbrains.com/idea/help/run-debug-configuration-application.html

Answer 3

大型数组的递归快速排序算法导致 Whosebug 错误。

试试 this link 中的非递归方法。以下Java代码由原始c代码转换而来，希望对您有所帮助。

static final int MAX_LEVELS = 1000;
public static boolean quickSort(int[] arr, int elements) {
    int i=0,L,R,pivot;
    int[] beg = new int[MAX_LEVELS], end = new int[MAX_LEVELS];
    beg[0]=0;
    end[0]=elements;
    while(i>=0) {
        L=beg[i];
        R=end[i]-1;
        if(L<R) {
            pivot=arr[L]; if(i==MAX_LEVELS-1) return false;
            while(L<R) {
                while(arr[R]>=pivot&&L<R) R--; if(L<R) arr[L++]=arr[R];
                while(arr[L]<=pivot&&L<R) L++; if(L<R) arr[R--]=arr[L];
            }
            arr[L]=pivot;
            beg[i+1]=L+1;
            end[i+1]=end[i];
            end[i++]=L;
        } else {
            i--;
        }
    }
    return true;
}
// an example
public static void main(String[] args) {
    // construct the integer array
    int[] arr = new int[80000];
    for(int i=0;i<arr.length;i++) {
        arr[i]=(int)Math.random()*100000;
    }

    // sort the array
    quickSort(arr, arr.length);
}

既省时又不受 Whosebug 影响。

Answer 4

这是你的快速排序：

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) 堆栈 space。这对于实际实现来说太多了。不过，修复很简单——您在 smaller 分区上递归，然后循环查找较大的分区。在较小的分区上递归意味着你只使用 O(log(r-p)) 堆栈 space 无论如何：

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 5

您正在报告 80 千元素数组的堆栈溢出。您的代码在大约 10 秒内对我笔记本电脑上的 80 百万元素数组进行排序，没有任何问题。我没有看到任何堆栈溢出错误...

如果你有一个随机输入，你应该期望最大递归深度在 log₂(n) 的范围内，对于 n= 小于 30八千万。 quicksort wikipedia article有更详细的分析。基本上，除非你遇到了一个真正病态的情况（你所有的枢轴都很糟糕），否则你不应该期望看到如此多的递归以至于堆栈溢出。

但是，我确实必须修复代码中的几个逻辑错误才能真正获得有效排序（我没有得到完全排序的结果）。

修复随机数生成问题

(int)Math.random()*1000000 将 始终 return 为零 。您需要添加另一组括号以截断 after 乘法：(int)(Math.random()*1000000).

修复您的分区逻辑

您的分区方法几乎与Hoare partitioning scheme 的逻辑匹配。但是，您似乎有一些差一错误。如果将您的代码与维基百科中的代码进行比较，您会发现一些差异。

你设置了i=p和j=r，但应该是i=p-1和j=r+1。
您应该删除交换逻辑中的增量和减量，因此 a[i++] 应该只是 a[i]，而 a[j--] 应该只是 a[j].

这是我用来测试的代码：

public class QSort {

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

        int x = a[p];
        int i = p-1;
        int j = r+1;

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

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

    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);
        }
    }

    public static void main(String args[]) {
        int n = Integer.valueOf(args[0]);
        int[] xs = new int[n];
        for (int i=0; i<n; i++) {
            xs[i] = (int)(Math.random()*1000000);
        }
        quickSort(xs, 0, xs.length-1);
        for (int i=0; i<n-1; i++) {
            if (xs[i] > xs[i+1]) {
                System.out.println("ERROR");
                System.exit(-1);
            }
        }
        System.out.println("SORTED");
    }

}

Answer 6

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

大型数组的快速排序 stackoverflow 错误

Quick Sort stackoverflow error for large arrays

java

stack-overflow

arrays

sorting

algorithm

修复随机数生成问题

修复您的分区逻辑