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

回答

相关问题