Radix Сортировать Java - PullRequest
Новая
       7

Radix Сортировать Java

0 голосов
/ 15 ноября 2009

Добро пожаловать. У меня есть метод сортировки по основанию, который использует массив, чтобы пройти, но должен иметь другой массив (мусорное ведро), который будет хранить в пустой очереди. Я запутался в том, как сделать очередь за мусорными ведрами. У меня также есть метод findPlace, который находит место каждой цифры при вызове. Итак, вот что я получил. Может ли кто-нибудь помочь мне найти то, что мне не хватает? Большое спасибо за ваше время. 

public static void radix(int [] list){
       int [] bin = new int[10]; 
      ArrayQueue<Integer> part = new ArrayQueue<Integer>(); // EDIT What would I do with this queue?? 
      int num = 0; 
         for(int i=0;i<list.length;i++)
         {
            bin[i] = 0;  
          }

            for(int pass=0;pass<list.length;pass++)
           {
                for(int num=0;num<list.length;num++)
               {
                       int digit=findPlace(bin[pass], num);
                 }

                  bin[digit].add(list[num]); // add to the bin
            }
              // Put back into list
               for(int h=0; h<10; h++)
               {
                    while(!bin[h].isEmpty())
                    {
                       list[num] = bin[queueNum].remove();
                     num++;
                    }
              }
        }


public static int getPlace (int x, int place)
    {return x/place % 10;}

Я также создал метод для поиска сегмента, так что мне просто нужно знать, как поместить его в массив, я бы просто сделал это? part.add (getPlace (x, place));?

1 Ответ

3 голосов
/ 15 ноября 2009

Ваш массив bin не действует как очередь только потому, что вы этого хотите :) Массивы не имеют методов, таких как add() и remove(). У вас есть два варианта, как это исправить:

  • Запрограммируйте правильную обработку очередей самостоятельно: очередь состоит из массива и двух указателей на этот массив, которые обычно называются head и tail. Вам нужно написать свои собственные методы для добавления и удаления, которые будут работать с массивом и указателями, и позаботиться о пустой или переполняющейся очереди.

  • Использовать встроенный в Java класс Queue. Это задокументировано в Javadocs библиотеки. Не знаю, намерено ли ваше назначение создать собственную очередь.

Обновление с другой деталью:

Вы спрашивали, как извлечь одну цифру из числа. Работать проще всего из наименее значимых цифр (ЛСД), как это предлагается в статье в Википедии. Для этого:

  • Чтобы извлечь последнюю цифру, выполните digit = number % 10 (это операция по модулю). Вы получите целое число от 0 до 9 включительно.
  • Чтобы убрать последнюю цифру, просто разделите на 10. Затем вы можете снять другую цифру.
  • Так как вам нужно несколько раз смотреть n-ую последнюю цифру числа, вам бы лучше поместить эту функцию в отдельный метод.

Вы можете использовать свои 0-9, чтобы выбрать правильную очередь, чтобы поставить свой номер.

Когда вы закончите ставить все свои числа в 10 групп, вам нужно скопировать их оттуда обратно в один список. Затем повторяйте до тех пор, пока в любом числе, которое вы не обработали, остаются цифры.

...