java - 为什么我的快速排序有时会出现堆栈溢出？

Question

当我向此方法发送大小 > 900000 的数组时，大约有一半的时间会收到 StackOverflowError 。请帮助我理解为什么会发生这种情况以及如何解决它。

public static void quicksort2(int[] xs, int lo, int hi){
    int h,l,p,t;
    if (lo<hi){
        l = lo;
        h = hi;
        p = xs[hi];

        do {
            while( (l<h) && (xs[l] <= p) )
                l= l+1;

            while( (h > l) && (xs[h] >= p))
                h = h-1;

            if (l < h){
                t = xs[l];
                xs[l] = xs[h];
                xs[h] = t;
            }
        } while (l<h);
        xs[hi] = xs[l];
        xs[l] = p;

        quicksort2(xs, lo, l-1);
        quicksort2(xs, l+1,hi);

    }
}

我得到的具体错误是:

Exception in thread "main" java.lang.StackOverflowError
at sort.Sorters.quicksort2(Sorters.java:117)
at sort.Sorters.quicksort2(Sorters.java:117)
at sort.Sorters.quicksort2(Sorters.java:118)
at sort.Sorters.quicksort2(Sorters.java:117)
at sort.Sorters.quicksort2(Sorters.java:117)

然后还有更多同样的事情。引用的两行是递归调用。

Answer 1

您的快速排序实现很好。通过使用更好的变量名、在 while 语句中使用大括号、使用 l++ 和 h-- 代替 l=l+1 和 h=h-1 以及其他一些类似的小细节，可以稍微改进它。

问题是当你这样做时:

int[] willBlowUp = new int[1000000];
quicksort2(willBlowUp, 0, willBlowUp.size - 1);

这将产生一个StackOverflowError，因为这是一种退化情况，使调用堆栈与输入一样高。而且我不知道有哪个 JVM 的堆栈部门足够大，可以进行一百万次递归调用。

给定的数组仅包含一百万个零。所以，逆序排序或者排序前打乱顺序是没有希望的。 do 循环内的第一个 while 始终会移动 l 直到分区的最后，从而使递归调用的第二部分仅包含一个元素，而第一部分则包含其他所有内容。这意味着在每个递归级别，数组的未排序区域仅减少 1 项，而理想情况下应减少一半。

此外，由于 do 内的第一个 while 循环必须执行总共 5000 万亿次迭代(如果不是 StackOverflowError)，因此性能非常糟糕。

如果使用胖快速排序和洗牌，这种特殊情况就可以解决，但总有一种情况，即使从统计角度来看这个问题不太可能再次发生。假设(即使在打乱之后)您得到了一个由 1, 2, 3, 4, 5, ..., n 组成的数组。在这种情况下，快速排序会表现得很糟糕。

对此有一些解决方案，但它们都很复杂且困惑，例如混合算法、在数组的某些子集上有选择地切换到另一种算法、在选择主元之前分析数据的结构是什么，或者如果洗牌的输出不好则重新洗牌。