quickSort - StackOverflowException

我想寫一個quicksort算法。請看下面的代碼：quickSort - StackOverflowException

public static void quickSort(int[] tab, int lowIndex, int highIndex) { 
    if (tab.length == 0 || tab == null) { 
     return; 
    } 

    int i = lowIndex; 
    int j = highIndex; 

    int pivot = tab[tab.length/2]; 

    while (i <= j) { 
     while (tab[i] < pivot) { 
      i++; 
     } 
     while (tab[j] > pivot) { 
      j--; 
     } 

     if (i <= j) { 
      int c = tab[i]; 
      tab[i] = tab[j]; 
      tab[j] = c; 
      i++; 
      j--; 
     } 

     if (lowIndex < j) { 
      quickSort(tab, lowIndex, j); // error !!! 
     } 
     if (i < highIndex) { 
      quickSort(tab, i, highIndex); 
     } 
    } 

}

問題是線程「主」java.lang.StackOverflowError異常。哪裏不對？

來源

2013-02-15 Stuart

當您調用太多的方法而不返回時，會發生StackOverflowError。但是，要求人們發現代碼中的錯誤並不是特別有效。您應該使用調試器（或添加打印語句）來隔離問題，然後構造一個[最小測試用例]（http://sscce.org）。 – 2013-02-15 21:35:51

在第一個「if」語句中，我認爲應該是第一個「tab == null」檢查。 – qben 2013-02-15 21:36:51

檢查你的'pivot'元素爲dasblinkenlight說的。也許行if（i <= j）{'應該是'if（i qben 2013-02-15 21:40:57

這是錯誤的：

int pivot = tab[tab.length/2];

你必須找到在所提供的切片的支點，在tab不是全局。

int pivot = tab[lowIndex + (highIndex - lowIndex)/ 2];

此外，您的條件終止遞歸是錯誤的。表格的長度不會改變。你必須檢查是否lowIndex >= highIndex

來源

2013-02-15 21:41:41

是的，你是對的。謝謝！ – Stuart 2013-02-15 21:43:31

quickSort - StackOverflowException

回答

相關問題