简单的QuickSort算法给出堆栈溢出错误？ [英] Simple QuickSort Algorithm giving Stack Overflow Error?

问题描述

我的朋友有一个小问题，我知道了。他写了一个简单的（他在学校里得到它）QuickSort算法它产生了一个StackOverflow错误。我知道这意味着它在某个地方调用自己递归太多次了，但我无法得到逻辑错误 - 请帮助我！

My friend has a small problem and I'm at the end of my knowledge. He wrote a Simple (he got it in school) QuickSort Algorithm And it produces a StackOverflow Error. I know it means it calls itself recursive too many times somewhere, but I can't get the logical Error - please help me!

这是代码（我是省略一些代码只是为了在2个文本区域显示它：）

Here is the code (I'm leaving out some code as that is only to show it in 2 text areas):

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个数字相同，则不会溢出。

But, if We call it and the 2 numbers are the same, it gives no Overflow.

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

If more code is needed, here is the full Code on pastebin: http://pastebin.com/cwvbwXEu

推荐答案

首先，你在这里有一个无限循环：

First, you have an infinite loop here:

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

它必须是数组[j]

其次（并导致无限递归），第二次调用快速排序

Secondly (and leading to the infinite recursion), in the second call to quicksort

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

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

In recursion, you always need to shorten the range that you call yourself with, or else it'll be infinite. I haven't worked out exactly what you're doing, but I think you mean:

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

这篇关于简单的QuickSort算法给出堆栈溢出错误？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！