2009-11-15 22 views
0

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

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)) ;?

ответ

3

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

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

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

Update с другой детали:

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

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

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

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

+0

Да, вам придется инициализировать очередь в вашем методе сортировки; вероятно, неплохо также создать очередь. Что касается вашего алгоритма, это выглядит неправильно, но я недостаточно умен, чтобы сказать, как он должен выглядеть. –

+0

Ну, я прочитал запись в Википедии и нашел там раздел о том, как сделать сортировку радикса с помощью очередей . В соответствии с этим вам не нужно 1, а 10 очередей. Вы прочитали описание (или получили другое описание) и выяснили, что вам нужно сделать? –

+0

Да, но я не хочу делать домашнее задание для вас. Независимо от того, что вы используете для очереди, сделайте массив из 10 из них. Кроме того, см. Обновление ответа, выше. –