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

我的朋友有一个小问题，我在我的知识结束。他写了一个简单的（他在学校）QuickSort算法它会产生一个StackOverflow错误。我知道这意味着它会在某个地方多次调用递归，但我无法获得逻辑错误 - 请帮助我！提供堆栈溢出错误的简单QuickSort算法？

下面是代码（我要离开了一些代码，这只是显示它在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号码，它不会产生溢出。

如果需要更多的代码，这里是引擎收录的全码：http://pastebin.com/cwvbwXEu

来源

2014-01-27 Marenthyu

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

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

它需要array[j]

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

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

在递归中，你总是需要缩短自己调用的范围，否则将会是无限的。我还没有制定出你在做什么，但我认为你的意思是：

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

来源

2014-01-27 18:38:26 mackworth

这似乎是我的朋友从一个简单的抄板错误。谢啦。 – Marenthyu

还要注意，递归不应该在while循环中。快速排序是（1）将数组分成两组，一组全部低于你的“数据透视”中间数字和一个以上，然后（2）用一次调用将每个组排序，每组快速排序。 – mackworth

这一呼吁：

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

递归调用quicksort与获得通过的是，而不是一个调用相同的参数较小的子问题来解决。因此它会无限地缓和。

来源

2014-01-27 18:30:28

if (l<r) 
quicksort(array,l,r);

Isnt l总是小于r？这将导致无限递归，这就是为什么如果两个值都相同，您不会发生溢出。

来源

2014-01-27 18:31:33 user2535749

* doh *当然！对不起，我的哑巴XD - 感谢您的快速帮助！ – Marenthyu

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

回答

相关问题