Vorwort: Das Thema der Java -Datenstrukturen und -Algorithmen wird von Zeit zu Zeit aktualisiert. Die Leser können es herzlich überwachen. Dieser Artikel beginnt mit dem einfachsten Sortieralgorithmus - der Sortierung des Buckets und analysiert die Implementierungsideen, die Codeimplementierung, die Leistungsmerkmale und die anwendbaren Szenarien der Sortierung von Bucket.
0. Andere Sortieralgorithmus -Indizes
//www.vevb.com/article/120879.htm
1. Idee der Bucket Sortierung
Ein einfaches Beispiel:
Sortieren der englischen Testergebnisse von 6 Personen (1 ~ 10 Punkte). Wenn die Punktzahl [6, 5, 8, 8, 10, 9] ist, besteht die Idee, mit Eimern zu sortieren, die Herstellung von 10 Eimern, die Zahlen sind 1 ~ 10 in Sequenz, und die Bewertungen werden in die entsprechenden Eimer gelegt, wie 6 Punkte in den Nr. 6 -Eimer, und zwei 8 Punkte in die Nr. 8 Eimer. Dies ist die Grundidee des Bucket -Sortierens.
Tatsächlich ist dies nur eine einfache Version. Stellen Sie sich vor, die Sortierung der zu sortierenden Spannweite der Elemente, die relativ groß sind, wie z. B. 1 ~ 10.000, benötigen Sie 10.000 Eimer? Tatsächlich wird in diesem Fall ein Element nicht immer in einen Eimer platziert, aber oft werden mehrere Elemente in einen Eimer platziert. In der Tat haben echte Bucket -Sortier- und Hash -Liste das gleiche Prinzip.
In der tatsächlichen Sortierung werden die Elemente in jedem Eimer normalerweise mit anderen Sortieralgorithmen sortiert, sodass die Sortierung von Eimer in Kombination mit anderen Sortieralgorithmen häufiger verwendet wird.
2. Bucket Sortiercode
Nachdem Sie die Idee der Bucket -Sortierung analysiert haben, müssen Sie zunächst die Sortierung der Elemente kennen. Wenn Sie das oben genannte als Beispiel einnimmt, deklarieren Sie ein Array von Länge 10 als 10 Eimer und geben Sie die Ergebnisse nacheinander in den Eimer, der Wert des Eimers beträgt +1 und geben schließlich das Array -Index in umgekehrter Reihenfolge aus. Der Wert jeder Position des Arrays wird mehrmals ausgegeben, so dass die Basis -Eimer -Sortierung erreicht werden kann.
öffentliche Klasse Bucketsort {private int [] Eimer; private int [] Array; public bucketsort (int range, int [] array) {this.buckets = new int [Bereich]; this.Array = Array; } /*Sortieren* / public void sort () {if (array! }}}/*Sortieren Ausgabe*/public void sortout () {// Umkehrungsdaten für (int i = buckets.length-1; i> = 0; i-) {für (int j = 0; j <buckets [i]; j ++) {System.out.print (i+"/t"); }}}}Testcode:
public class sortest {public static void main (String [] args) {testBucketSSort (); } private statische void testbucketSSort () {int [] array = {5,7,3,5,4,8,6,4,1,2}; Bucketsort BS = New Bucketsort (10, Array); bs.sort (); bs.sortout (); // Ausgabedrucken sortieren}}3.. Eimer -Sortierleistung Eigenschaften
Die Sortierung von Bucket muss tatsächlich nur durch alle Elemente sortiert werden und sie dann nacheinander in die angegebene Position bringen. Wenn die Ausgangssortierzeit hinzugefügt wird, müssen alle Eimer durchquert werden. Daher ist die zeitliche Komplexität der Eimersortierung O (N+m), n ist die Anzahl der zu sortierten Elemente, und M ist die Anzahl der Eimer, dh der Bereich der zu sortierten Elemente. Dieser Algorithmus ist ein sehr schneller Sortieralgorithmus, aber die räumliche Komplexität ist relativ groß.
Wenn der Größenbereich der zu angeordneten Elemente relativ groß ist, aber die Anzahl der zu angeordneten Elemente relativ gering ist, ist Raumabfälle schwerwiegender. Die zu ordnungsgemäße Verteilung der Elemente ist jeden Monat einheitlich, und je höher die Raumnutzungsrate, ist dies tatsächlich selten.
Durch die obige Leistungsanalyse können wir die Eigenschaften der Eimersortierung erhalten: schnell und einfach, aber gleichzeitig ist die Raumnutzung niedrig. Wenn die zu sortierenden Daten groß sind, ist die Raumnutzungsrate unerträglich.
4. Eimersortierende Szenarien
Gemäß den Eigenschaften der Bucket -Sortierung ist die Sortierung der Bucket im Allgemeinen für bestimmte Umgebungen anwendbar, z. B. der Datenbereich ist relativ begrenzt oder es gibt einige spezifische Anforderungen, z. All dies basiert jedoch auf der Bestätigung des Umfangs der Daten. Wenn die Umfangsspanne zu groß ist, sollten Sie andere Algorithmen verwenden.