java - 简单的快速排序算法会出现堆栈溢出错误吗？

Question

我的 friend 遇到了一个小问题，而我已经无能为力了。他写了一个简单的(他在学校学到的)快速排序算法，它产生了一个 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);

但是，如果我们调用它并且两个数字相同，则不会出现溢出。

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

Answer 1

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

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

它必须是数组[j]

其次(并导致无限递归)，在第二次调用快速排序时

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

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

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