不一致的快速排序 StackOverflowError

Question

我正在研究仅递增整数的数组的快速排序问题。此例程中的主元选择始终是子数组的第一个元素（由问题决定），并且在某个时刻我预计这会导致 StackOverflowError。奇怪的是，它不适用于大小 n = ~25,000 到 ~404,300 的问题，但它适用于 n 比这大得多的问题。即使当我为数组的输入添加种子时，它也会波动，有时适用于 n = 10,000，有时则不适用。

以下是我得到的一些结果（时间以秒为单位）：

10,000: .077

20,000: .282

~25,000 - ~404,300: SOE

405,000 - 3.169

410,000 - 1.632

450,000 - .098

500,000 - .059

5,000 ,000 - .634

10,000,000 - 1.337

100,000,000 - 18.613

有什么想法会导致这种情况吗？代码如下。

提前致谢。

public static void main(String[] args) {
    int arraySize = 1000000;
    int[] a = new int[arraySize];
    Random gen = new Random();

    gen.setSeed(0);
    a[0] = gen.nextInt(arraySize * 10);
    for (int i = 1; i < arraySize; i++) {
        a[i] = a[i - 1] + gen.nextInt(arraySize / 10);
}


private static void quickSort(int[] a, int lo, int hi) {
    if (hi <= lo) return;
    int j = partition(a, lo, hi);
    quickSort(a, lo, j - 1);
    quickSort(a, j + 1, hi);
}

private static int partition(int[] a, int lo, int hi) {
    int i = lo, j = hi + 1;
    int pivot = a[i];
    while (true) {
        while (a[++i] > pivot) if (i == hi) break;
        while (pivot > a[--j]) if (j == lo) break;
        if (i >= j) break;
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    int temp = a[lo];
    a[lo] = a[j];
    a[j] = temp;
    return j;
}

Answer 1

我认为您的分区方法不正确（但我可能是错的，我只是浏览了代码），因此数据未正确分区，导致更多的递归调用导致堆栈溢出。

我建议您向快速排序方法添加一个打印行，该方法打印出其参数，以便您可以将其转换为线图，其中 X 值是调用号（即第 1 行用于第一次调用，第 2 行用于下一次调用等），并绘制一条线 (X, Y1)-(X,Y2)，其中 Y1 是第一个值，Y2 是第二个值。

我的猜测是，您现在会很容易地看到出了什么问题（也许会降低排序的数量）。