不一致Quicksort StackOverflowError

我正在为只增加整数数组的快速排序问题工作。在这个例程中的pivot选项总是子数组的第一个元素（如问题指出的那样），并且在某个点我期望这导致StackOverflowError。奇怪的是，它不适用于大小为n = 25,000到〜404,300的问题，但是它比n大得多。即使我输入数组的输入，它也会波动，有时n = 10,000，有时不工作。不一致Quicksort StackOverflowError

这里有一些结果我得到了（时间以秒为单位）：

10000：0.077

20000:1 .282

〜25000 - 〜404300：SOE

405000 - 3.169

410,000 - 1.632

450,000 - .098

50 - .059

500 - 0.634

1000 - 1.337

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

来源

2011-03-06 Cody

听起来像你正在进入一个无限循环/递归的地方。 – Oded 2011-03-06 20:19:54

是的，但奇怪的是，它会为特定范围的数字做到这一点，然后再次开始工作。例如，它有时适用于n = 10,000，并且对于该n其他时间不起作用。不知道错误在哪里。 – Cody 2011-03-06 20:25:36

好吧，你在这里使用一个随机的种子......看看你是否可以用一个常数重现，当你这样做的时候，通过调试。 – Oded 2011-03-06 20:29:22

我觉得你的划分方法是不正确的（但我可能是错的，我只脱脂的代码），因此数据不分区正确导致更多的递归调用导致堆栈溢出。

我建议你在quicksort方法中添加一个打印行，打印出它的参数，这样你就可以将它转换为一个线图，其中X值是调用号（例如，第1行用于第一个调用，第二行用于下一次调用等），并绘制一条线（X，Y1） - （X，Y2），其中Y1是第一个值，Y2是第二个。

我的猜测是，你现在很容易就能看到出了什么问题（可能会降低排序的数量）。

来源

2011-03-06 20:51:57

不一致Quicksort StackOverflowError

回答

相关问题