我正在尝试编写一个程序,使用递归和快速排序(如分区)来查找第 k 个最小元素,以便不必对整个数组进行排序。我觉得我的代码应该可以工作,但是当调用该函数时我立即收到堆栈溢出错误,因此我无法测试它。
我认为堆栈溢出与溢出执行堆栈有关,并且我知道它是在递归中发生的,但错误是在函数的第一行调用的,所以它让我感到困惑。如果有人可以看看这个并提出一些建议,我将非常感激。谢谢。
public static int find_kth_smallest( int[] A, int n, int k )
{
int[] Left = new int[200];
int[] Right = new int[200];
int half = n/2;
int x = 0; int j = half + 1; int q = 0;
int count = 0;
int pivot = A[half];
for(int i = 0; i < n; i++)
{
if(A[i] < pivot)
{
Left[x] = A[i];
x++;
}
if(A[i] > pivot)
{
Right[j] = A[i];
j++;
}
}
while(Left[q] != 0)
q++;
if(k < q)
{
return find_kth_smallest(Left, q, k);
}
if(k > q)
{
return find_kth_smallest(Right, n-q, k);
}
if(k-1 == q)
{
return A[pivot];
}
return -1;
最佳答案
你的错误是j
应该从0
开始,而不是half+1
。目前,您正在将数组中枢轴上方的部分复制到 Right
的上半部分。如果您遵循递归的右侧,则可以保证在该点之后主元将永远保持等于 0
,因此您永远不会停止递归。
此外,这里还有其他几个问题:
- 您假设
A
中没有任何元素等于0
,这是一个危险的假设。 - 您使用的是固定的
int[200]
。这是Java;你可以在运行时分配这些东西。只需根据n
适当调整Right
和Left
的大小即可。现在,对于大小为 400 或更大的每个A
,您的程序都会失败。
关于java - Java 中的堆栈溢出错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15215440/