Переполнение стека в Java QuickSort на массиве - PullRequest
Новая
       44

Переполнение стека в Java QuickSort на массиве

2 голосов
/ 21 мая 2011

Кто-нибудь знает, почему я получаю переполнение стека на моей быстрой сортировке в следующем коде?: 

   private int[] concat( int[] less, int inxl, int pivot, int inxm, int[] more )
   {

      int[] concated = new int[ less.length ];

      for( int inx = 0; inx < inxl; inx++ )
      {

         concated[ inx ] = less[ inx ];

      }

      concated[ inxl ] = pivot;
      inxl++;

      for( int inx = 0; inx < inxm; inx++ )
      {

         concated[ inxl ] = more[ inx ];
         inxl++;

      }      

      return concated;

   }

   private int[] quickSort( int[] array )
   {

      if( array.length <= 1 )
         return array;

      int[] less = new int[ array.length ];
      int[] more = new int[ array.length ];
      int inxl = 0, inxm = 0;

      for( int inx = 1; inx < array.length; inx++ )
      {

         if( array[ inx ] < array[ 0 ] )
         {

            less[ inxl ] = array[ inx ];
            inxl++;

         }
         else
         {

            more[ inxm ] = array[ inx ];
            inxm++;

         }

      }

      return concat( quickSort( less ), inxl, array[ 0 ], inxm, quickSort( more ) );

   }

Любая помощь будет принята с благодарностью. Я готовлюсь к собеседованию и немного подзабыл, поэтому время имеет большое значение. Спасибо заранее! :)

С уважением, Петр.

Ответы [ 2 ]

6 голосов
/ 21 мая 2011

Ваш quickSort метод рекурсии неверен.Он должен вызывать себя с меньшими массивами (или с некоторым другим параметром, который становится меньше), а не с массивами такой же длины.Вот почему вы получаете бесконечную рекурсию, которая выглядит как StackOverflowError.

0 голосов
/ 21 мая 2011

Интересно, вечно ли ты возвращаешься. Где вы уменьшаете размер массива в вашем методе быстрой сортировки? Вы использовали println для определения размера массива, чтобы увидеть, становится ли он меньше?

...