小编典典

提供堆栈溢出错误的简单QuickSort算法?

java

我的朋友有一个小问题,我已不知所措。他编写了一个简单的(在学校就读到的)QuickSort算法,它产生了StackOverflow错误。我知道这意味着它在某处多次调用自身递归,但是我无法获得逻辑错误-
请帮助我!

这是代码(我在这里省略了一些代码,仅是为了在2个文本区域中显示它):

int array [] = new int [10];
...
 public static void quicksort (int array[],int l,int r){
int i = l;
int j = r;
int mitte = array [(l+r)/2];

while (i<j) {
  while  (array[i]<mitte) {
    i++;
  } // end of if
  while  (mitte<array[i]) {
    j--;
  } // end of if
  if (i<=j) {
    int merke =array[i];
    array[i] = array [j];
    array [j] = merke ;
    i++;
    j--;
  } // end of if
  if (i<j) {
    quicksort(array,l,j);
  } // end of if
  if (l<r) {
    quicksort(array,l,r);
  } // end of if
} // end of while
}

它的名称如下:

 quicksort(array,0,9);

但是,如果我们将其称为2个数字相同,则不会产生溢出。

如果需要更多代码,这是pastebin上的完整代码:http :
//pastebin.com/cwvbwXEu


阅读 245

收藏
2020-11-30

共1个答案

小编典典

首先,这里有一个无限循环:

while  (mitte<array[i]) {
    j--;
  } // end of if

它必须是 array[j]

其次(并导致无限递归),在第二次对quicksort的调用中

if (l<r) {
  quicksort(array,l,r);
} // end of if

递归时,您总是需要缩短自己的调用范围,否则它将是无限的。我还没有弄清楚您在做什么,但我认为您的意思是:

if (i<r) {
   quicksort(array,i,r);
 } // end of if
2020-11-30