快速排序和中位執行堆棧溢出錯誤

Question

首先，我只是想說明這是一個我已經做了大量嘗試的作業問題。

我被要求來修改快速排序中的Java設置樞軸爲使用下式​​

我寫一個computeMedian方法，該方法接受3點的整數數組中的9個值的僞中間值，確定最高的，然後返回該值。

的代碼：

public static int computeMedian(int x, int y, int z) 
    { 
     if((x >= y && x <= z) || (x >= z && x <= y)) {return x;} 
     else if((y >= x && y <= z) || (y >= z && y <= x)) {return y;} 
     else if((z >= x && z <= y) || (z >= y && z <= x)) {return z;} 
     else { return 0; } 
    } 

然後我用它在我findPivot方法，該方法對當前array, from, to值，並使用它們來構建樞軸

下面是代碼：

public static int findPivot(int[] a, int from, int to) 
    { 
     if(a.length <= 7) 
     { 
      return a[(to)/2]; 
     } 
     else if(a.length > 7 && a.length <= 40) 
     { 
      return computeMedian(a[from], a[(to)/2] , a[to]); 
     } 
     else 
     { 
      int x = computeMedian(a[0 * (to)/8], a[1 * (to)/8], a[2 * (to)/8]); 
      int y = computeMedian(a[3 * (to)/8], a[4 * (to)/8], a[5 * (to)/8]); 
      int z = computeMedian(a[6 * (to)/8], a[7 * (to)/8], a[8 * (to)/8]); 
      return computeMedian(x,y,z); 
     } 
    } 

此方法對於排序小於或等於40的任何數組工作正常，但只要它大於40，我會收到堆棧溢出錯誤回到我在else {}部分中的computeMedian方法。我會注意到，return computeMedian(a[from], a[(to)/2] , a[to]);如果我把它放在> 40的部分，但這只是3個值的中值，而不是3箇中值的中值。

目前，這是我怎麼也findPivot插入快速排序劃分方法：

private static int modPartition(int[] a, int from, int to) 
    { 
     int pivot = findPivot(a, from, to); 
     int i = from - 1; 
     int j = to + 1; 
     while(i < j) 
     { 
      i++; while (a[i] < pivot) { i++; } 
      j--; while (a[j] > pivot) { j--; } 
      if (i < j) { swap(a, i, j); } 
     } 
     return j; 
    } 

我幾乎難倒爲什麼我的computeMedian方法無法適用於大型數據集。我試圖通過for循環將i * (n-1)/8值放入數組中，將它們排序並在中間返回值以及將值放入數組p並調用computeMedian(computeMedian(p[0], p[1], p[2]), computeMedian(p[3],p[4],p[5]),...etc，並且我得到相同的堆棧溢出問題，但它傾向於轉移到我的代碼的不同部分並引導我進入圈子。

我可以發佈任何更多的片段，如果任何人需要，但我認爲我的問題可能在這裏。

感謝您的幫助。我仍然在學習，我認爲掌握這一點將完全幫助我自己解決未來的問題。

這裏是從堆棧跟蹤的問題行： 第16行：int p = modPartition(a, from, to); 線18 modSort(a, p+1, to); 線23 int pivot = findPivot(a, from, to);

我的繼承人整個modSort方法也：

​​

Answer 1

轉載和糾正

代碼添加到重現錯誤...

private static void swap(int[] a, int i, int j) { 
    int tmp = a[i]; 
    a[i] = a[j]; 
    a[j] = tmp; 
} 

public static void main(String[] args) { 
    // Generate a sample 
//  ArrayList<Integer> list = new ArrayList<>(64); 
//  for (int i = 0; i < 64; i++) list.add(i); 
//  Collections.shuffle(list); 
//  System.out.println(list); 
    int[] arr = {40, 9, 2, 62, 8, 42, 46, 23, 61, 45, 63, 48, 43, 36, 33, 32, 1, 55, 7, 17, 16, 25, 5, 26, 22, 11, 56, 38, 60, 31, 58, 29, 51, 34, 24, 54, 4, 3, 30, 20, 57, 18, 50, 44, 41, 12, 59, 6, 53, 39, 37, 35, 28, 13, 14, 15, 0, 19, 49, 52, 21, 27, 47, 10}; 

    modSort(arr, 0, arr.length-1); 

    System.out.println(Arrays.toString(arr)); 
} 

調試。爲StackOverFlowError設置斷點（如註釋中所建議的）不起作用。所以我在線上尋找一個正常的斷點（modSort開始）。

對於此示例數據，開始通過modSort與from=3;to=5進行無限遞歸。對於這個範圍來說，p = 2，這看起來不正常。

我責怪findPivot(a,from,to)方法。對於整個a找到一個關鍵點看起來不錯，但不是一個範圍。嘗試此更正：

public static int findPivot(int[] a, int from, int to) { 
    final int rangeLength = to - from + 1; 
    if(rangeLength <= 7) { 
     return a[(from + to)/2]; 
    } else if(rangeLength <= 40) { // why test "a.length > 7" ? 
     return computeMedian(a[from], a[(from + to)/2] , a[to]); 
    } else { 
     final int rangeLength_8 = (to - from)/8; 
     int x = computeMedian(a[from], a[from + rangeLength_8], a[from + 2 * rangeLength_8]); 
     int y = computeMedian(a[from + 3 * rangeLength_8], a[from + 4 * rangeLength_8], a[from + 5 * rangeLength_8]); 
     int z = computeMedian(a[from + 6 * rangeLength_8], a[from + 7 * rangeLength_8], a[to]); 
     return computeMedian(x,y,z); 
    } 
} 

然後，它對我的​​示例正常工作。我在這一點上停下來（必須睡一覺）。

我認爲你應該嘗試熟悉調試器。我認爲你應該更容易弄清楚。

Answer 2

現在你已經實際上包含了代碼和堆棧溢出問題的錯誤消息，我們可以幫助你。

從您的堆棧跟蹤中，我們可以看到無限遞歸是可能是第二次調用modSort，因爲第18行是重複的。

由於該調用和傳入參數之間的唯一區別是第二個參數，所以我打賭p的金額小於from。

最好的方法來確認是插入一個很好的老式print聲明。

public static void modSort(int[]a, int from, int to) 
{ 
    if(from >= to) { return; } 
    int p = modPartition(a, from, to); 
    System.out.println("from=" + from + ", to=" + to + ", p=" + p); 
    modSort(a, from, p); 
    modSort(a, p+1, to); 
} 

由此產生的輸出應該顯示出一個非常明確的模式。