不一致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

回答

相關問題