Radixsort Java

Question

Willkommen. Ich habe ein radix Sortierverfahren, das ein Array verwendet, um zu gehen, aber hat eine andere Anordnung haben (ist), der in einer leeren Warteschlange gespeichert werden. Ich bin verwirrt, wie ich eine Warteschlange für die Fächer machen würde. Ich habe auch eine findPlace Methode, die an die Stelle der jede Ziffer findet, wenn aufgerufen. So, hier ist das, was ich habe. Kann jemand mir helfen, zu finden, was mir fehlt? Vielen Dank für Ihre Zeit.

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;}

Ich habe auch eine Methode, um die Eimer zu finden, so dass ich nur wissen müssen, wie ich es in ein Array setzen würde, würde ich dies nur tun? part.add (getPlace (x, Ort));?

Answer 1

Ihr Array, bin wirkt nicht wie eine Schlange, nur weil Sie es :) Arrays wollen nicht über Methoden wie add() und remove(). Sie haben zwei Möglichkeiten, wie Sie dieses Problem zu beheben:

• Programm im richtigen Umgang für Warteschlangen selbst: Eine Warteschlange besteht aus einem Array und zwei Zeiger in dieses Array, traditionell genannt head und tail. Sie müssten Ihre eigenen Methoden schreiben, hinzuzufügen und zu entfernen, die mit dem Array und den Zeigern und kümmern sich um eine leere Warteschlange oder einen überquell ein.

funktionieren würde

• Mit Java-interner Queue-Klasse. Es ist in der Bibliothek Javadocs dokumentiert. Weiß nicht, ob Ihre Aufgabe beabsichtigt, damit Sie Ihre eigene Warteschlange zu bauen, though.

Aktualisieren mit einem anderen Detail:

Sie gefragt, wie eine einzelne Ziffer von einer Zahl zu extrahieren. Es ist am einfachsten Arbeiten aus den am wenigsten signifikanten Stellen (LSD), wie in dem Wikipedia-Artikel vorgeschlagen. Um dies zu tun:

• Um die letzte Ziffer zu extrahieren, zu tun digit = number % 10 (die die Modulo-Operation ist). Sie erhalten eine ganze Zahl zwischen 0 und einschließlich 9 erhalten.
• Um die letzte Ziffer abzustreifen, teilen Sie einfach von 10. Dann können Sie eine weitere Ziffer abziehen.
• Da Sie an der n-ten letzten Ziffer einer Zahl mehrmals müssen zu suchen, würden Sie gut tun, um diese Funktionalität in ein separates Verfahren setzen.

Sie können Sie 0 bis 9 die richtige Warteschlange wählen Sie Ihre Nummer an zu setzen.

Wenn Sie fertig sind Warteschlangen alle Ihre Zahlen in die 10 Eimer, müssen Sie sie von dort wieder in eine einzige Liste kopieren. Dann so lange wiederholen, wie es noch in einer beliebigen Anzahl sind Ziffern, die Sie nicht bearbeitet haben.