1

配列全体をソートする必要がないように、再帰とパーティショニングのようなクイックソートを使用して 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;
4

2 に答える 2

0

もちろん

if(k-1 == q)
   {

決して真実ではありません。

if(k > q)
   {

それをシールドします。

于 2013-03-12T14:28:15.040 に答える
0

あなたのエラーは、ではなくでj開始する必要があることです。現在、ピボットの上にある配列の部分を の上半分にコピーしています。再帰の右側をたどると、ピボットがその時点以降も永遠に等しいことが保証されるため、再帰を停止することはありません。0half+1Right0

また、ここには他にもいくつかの問題があります。

  • Aのどの要素もと等しくないと仮定していますが0、これは危険な仮定です。
  • あなたは固定int[200]のものを使用しています。これは Java です。これらを実行時に割り当てることができます。に基づいて適切なサイズにRightします。現在、プログラムはサイズが 400 以上の場合に失敗します。LeftnA
于 2013-03-05T03:56:27.447 に答える