Der Versuch, über den folgenden Code Bucketsort Code

Question

Ich habe drei Fragen zu verstehen:

static void funct(int[] list) { 
    final int N = 20; 

    java.util.ArrayList[] buckets = new java.util.ArrayList[N]; 
    for(int i = 0; i< list.length; i++) { 
    int key = list[i]; 
    if(buckets[key] = null) 
      buckets[key].add(list[i]); 
    } 
    int k = 0 
    for(int i = 0; i <buckets.length; i++) { 
     if(buckets[i] != null) { 
      for(int j = 0; j< buckets[i].size(); j++) 
       list[k++] = (Integer)buckets[i].get(j); 
     } 
    } 

}

1. Der Algorithmus hat ein großes Manko, ist es, dass es nur für bis arbeiten 20 Elemente und dass es eine geringe Komplexität hat?

2. Der Punkt des Codes ist eine Liste von Elementen zu sortieren - sie werden in ein Array, dann in Eimer gelegt, dann werden sie aus den Eimern wieder in das Array gesetzt?

3. Heres der eine, auf den ich bin, wie würden Sie die Methode ändern, so dass Sie ein Array übergeben könnten, das Objekte einer anderen Klasse statt Ganzzahlen enthält?

Answer 1

Addressing Ihre Fragen:

1. , dass zwei Mängel ist. Vergiss die Komplexität für einen Moment. überlegen, wie es für mehr als 20 Elemente funktionieren soll. Für eine Bucket-Sortierung lautet die Idee, dass Sie einen Bucket basierend auf der Position des Elements im gesamten Bereich der Elemente auswählen. Der einfachste Weg, dies auf einem Computer mit binären Ganzzahlen zu tun, besteht darin, die ersten paar Bits (die höchstwertigen Bits) in der Zahl auszuwählen und eine Potenz von zwei Buckets zu verwenden, z. B. 16 oder 32. Sie können Holen Sie sich die wichtigsten Bits (und damit den Bucket) mit einer und Operation (&). Sie können dann die Bits verwenden, um den Bucket direkt auszuwählen.

2. Die Idee hinter bucket sort besteht darin, ein Element der Radix-Sortierung für einen ersten Durchgang über die Eingabe zu verwenden und dann eine andere Sortierung (oder eine iterierte Radix-Sortierung) für die kleinen Buckets zu verwenden leicht sortiert, oder die Verkettung aller Buckets (z. B. zurück in das Array) kann mit geringerer Komplexität sortiert werden.

3. Die Bucket-Sortierung basiert auf der Kenntnis des gesamten Eingabebereichs, sodass Sie diesen Bereich in Segmente aufteilen und dann die Eingaben einzeln kategorisieren können. Am einfachsten ist dies, wenn die Eingabe numerisch ist. Wenn die Reihenfolge in der Eingabe nur relativ ist und keine absoluten Werte bekannt sind und es keine einfache Möglichkeit gibt, herauszufinden, wo im gesamten Bereich ein Element ist, dann ist Bucket-Sortierung nicht geeignet.

Answer 2

Dies ist eine gute Hausaufgabe Frage. Viele der Fragen sind subjektiv und hängen sehr wahrscheinlich von Ihrer Klasse ab.

Ich schlage vor, Sie machen einen Stich selbst, weil die Klassenstunden eine bessere Vorstellung davon geben, wonach der Ausbilder sucht, als irgendwelche Antworten hier.

Außerdem, wenn jemand außerhalb eines Klassenzimmers dies sah, wäre die Antwort, nur die eingebaute Array-Sortierung zu verwenden und diesen Müll wegzuwerfen!