Ошибка переполнения стека в Java

Я пытаюсь закодировать программу, которая находит k-й наименьший элемент, используя рекурсию и быструю сортировку, такую как разбиение на разделы, чтобы не сортировать весь массив. Я чувствую, что мой код должен работать, но я получаю ошибку переполнения стека сразу, когда вызывается функция, поэтому я не могу ее протестировать.Ошибка переполнения стека в Java

Я думал, что переполнение стека связано с переполнением стека выполнения, и я понимаю, что это происходит с рекурсией, но ошибка вызывается в первой строке функции, поэтому меня это смущает. Если кто-то может взглянуть на это и дать некоторые предложения, я бы очень признателен. Благодарю.

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;

источник

2013-03-05 Josephine

Каковы значения, которые вы передаете в качестве параметров функций? – Thihara

Непонятно, как вы отлаживали это. Просто вмешательство в метод не должно вызывать проблемы ... –

его умрет на первой строке, если он рекурсивный. Его просто так, что он не первый раз был на первой строке, так много раз повторялся, что закончился из стека –

Ваша ошибка в том, что j должна начинаться 0, не half+1. В настоящее время вы копируете часть вашего массива, которая находится выше точки поворота, в верхнюю половину Right. Если вы когда-либо будете следовать правой стороне рекурсии, вам гарантируется, что точка опоры навсегда останется равной 0 после этого момента, поэтому вы никогда не прекратите рекурсию.

Кроме того, есть несколько других проблем здесь:

Вы предполагаете, что ни один элемент не A равно 0, что опасное предположение.
Вы используете фиксированный int[200]. Это Java; вы можете выделить эти вещи во время выполнения. Просто позвольте Right и Left быть соответствующим образом на основе n. Прямо сейчас ваша программа будет сбой для каждого A размером 400 или больше.

источник

2013-03-05 03:56:27 charleyc

Конечно

if(k-1 == q) 
    {

никогда не будет верно, как

if(k > q) 
    {

щитами его.

источник

2013-03-12 14:28:15

Ошибка переполнения стека в Java

ответ

Смежные вопросы