Detaillierte Erläuterung der Methode der Bucket-Sortierung des Java-Zahlenvervollständigungsalgorithmus

Dieser Artikel stellt hauptsächlich die Java-Datenstruktur und die Implementierungsmethode für die Bucket-Sortierung vor. Er analysiert das Konzept, das Prinzip, die Implementierungsmethode und die damit verbundenen Betriebsfähigkeiten der Bucket-Sortierung im Detail anhand konkreter Beispiele.

Das Beispiel in diesem Artikel beschreibt die Implementierungsmethode der Bucket-Sortierung der Java-Datenstruktur und des Algorithmus. Teilen Sie es wie folgt als Referenz mit allen:

Grundidee:

Angenommen, die Eingabe wird durch einen zufälligen Prozess generiert [0 , M ) gleichmäßig verteilte reelle Zahlen auf dem Intervall. Teilen Sie das Intervall [0, M) in n Unterintervalle (Buckets) gleicher Größe auf, weisen Sie diesen Buckets n Eingabeelemente zu, sortieren Sie die Elemente in den Buckets und verbinden Sie dann die Bucket-Eingänge 0 ≤ A[1.. n] ArrayB[0..n-1] ist ein Array von Zeigern, die auf den Bucket (verknüpfte Liste) zeigen. Verteilen Sie n Datensätze an jeden Bucket. Wenn mehr als ein Datensatz demselben Bucket zugeordnet ist, ist eine Sortierung innerhalb des Buckets erforderlich. Listen Sie abschließend die Datensätze in jedem Bucket der Reihe nach auf und merken Sie sich diese in einer geordneten Reihenfolge.

[Bucket - Keyword] MappingFunktion

bindex=f(key) Wobei Bindex der Bucket ist Index des Arrays B (d. h. des Bindex-Buckets), k ist der Schlüssel der zu sortierenden Spalte. Der Schlüssel zur Effizienz der Bucket-Sortierung liegt in dieser Zuordnungsfunktion, die Folgendes tun muss: Wenn das Schlüsselwort k1Natürlich Die Bestimmung der Zuordnungsfunktion steht in engem Zusammenhang mit den Eigenschaften der Daten selbst Geben wir unten ein Beispiel:

Wenn die zu sortierende Spalte K= { ist. 49, 38, 35, 97, 76, 73, 27, 49}. Diese Daten liegen alle zwischen 1 und 100. Daher passen wir 10 Buckets an und bestimmen die Zuordnungsfunktion f(k)=k/10. Dann wird das erste Schlüsselwort 49 im 4. Bucket positioniert (49/10=4). Stapeln Sie alle Schlüsselwörter nacheinander in Buckets und führen Sie eine schnelle Sortierung in jedem nicht leeren Bucket durch, um das folgende Bild zu erhalten:

Solange die Reihenfolge des obigen Bildes ausgegeben wird die Daten in jedem B[i], um eine geordnete Sequenz zu erhalten.

Der Kerncode des Algorithmus lautet wie folgt:

/// <summary>
/// 桶排序
///
///如果有重复的数字,则需要 List<int>数组,这里举的例子没有重复的数字
/// </summary>
/// <param name="unsorted">待排数组</param>
/// <param name="maxNumber">待排数组中的最大数,如果可以提供的话</param>
/// <returns></returns>
static int[] bucket_sort(int[] unsorted, int maxNumber = 97)
{
 int[] sorted = new int[maxNumber + 1];
 for (int i = 0; i < unsorted.Length; i++)
 {
  sorted[unsorted[i]] = unsorted[i];
 }
 return sorted;
}
static void Main(string[] args)
{
 int[] x = {49、 38 、 35、 97 、 76、 73 、 27、 49 };
 var sorted = bucket_sort(x, 97);
 for (int i = 0; i < sorted.Length; i++)
 {
  if (sorted[i] > 0)
   Console.WriteLine(sorted[i]);
 }
 Console.ReadLine();
}

Eimer-Sortierkostenanalyse

Bucket-Sortierung nutzt die Zuordnungsbeziehung von Funktionen, um fast den gesamten Vergleichsaufwand zu reduzieren. Tatsächlich entspricht die Berechnung des f(k)-Werts der Bucket-Sortierung der Aufteilung bei der Schnellsortierung, bei der eine große Datenmenge in grundsätzlich geordnete Datenblöcke (Buckets) unterteilt wird. Dann müssen Sie nur eine erweiterte Vergleichssortierung für eine kleine Datenmenge im Bucket durchführen.

Die zeitliche Komplexität der Bucket-Sortierung von N Schlüsselwörtern ist in zwei Teile unterteilt:

(1) SchleifeBerechnen Sie dieses Mal den Bucket jeder Schlüsselwort-Zuordnungsfunktion Komplexität ist O(N).
(2) Verwenden Sie den erweiterten Vergleichssortierungsalgorithmus, um alle Daten in jedem Bucket zu sortieren. Seine zeitliche Komplexität beträgt ∑ O(Ni*logNi). Wobei Ni das Datenvolumen des i-ten Buckets ist.

Offensichtlich ist Teil (2) der entscheidende Faktor für die Leistung der Eimersortierung. Die Minimierung der Datenanzahl im Bucket ist die einzige Möglichkeit, die Effizienz zu verbessern (da die beste durchschnittliche Zeitkomplexität basierend auf der Vergleichssortierung nur O(N*logN) erreichen kann). Daher müssen wir unser Bestes geben, um die folgenden zwei Punkte zu erreichen:

(1) Die Zuordnungsfunktion f(k) kann N Daten gleichmäßig auf M Buckets verteilen, sodass jeder Bucket [ N /M] Datenmenge.
(2) Erhöhen Sie die Anzahl der Eimer so weit wie möglich. Im Extremfall kann aus jedem Bucket nur ein Datenwert abgerufen werden, wodurch der Sortiervorgang „Vergleich“ der Daten im Bucket vollständig vermieden wird. Dies ist natürlich nicht einfach, wenn die Datenmenge groß ist, führt die Funktion f(k) zu einer großen Anzahl von Bucket-Sets, was zu einer erheblichen Platzverschwendung führt. Dies ist ein Kompromiss zwischen Zeitkosten und Platzkosten.

Für N zu sortierende Daten und M Buckets beträgt die durchschnittliche Bucket-Sortierzeitkomplexität von [N/M] Daten pro Bucket:

O (N)+ O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)

Wenn N=M, also im Extremfall, gibt es in jedem Bucket nur einen Datenwert. Die beste Effizienz der Bucket-Sortierung kann O(N) erreichen.

Zusammenfassung: Die durchschnittliche zeitliche Komplexität der Bucket-Sortierung ist linear O(N+C), wobei C=N*(logN-logM). Im Verhältnis zum gleichen N ist die Effizienz umso höher, je größer die Anzahl der Buckets M ist, und die beste Zeitkomplexität erreicht O(N). Natürlich beträgt die Platzkomplexität der Bucket-Sortierung O(N+M). Wenn die Eingabedaten sehr groß sind und die Anzahl der Buckets auch sehr groß ist, sind die Platzkosten zweifellos teuer. Darüber hinaus ist die Eimersortierung stabil.

Die folgenden drei Punkte:

1. Die Eimersortierung ist stabil
2. Die Eimersortierung ist die schnellste unter den gängigen Sortierungen, besser als die Schnellsortierung. Noch schneller. ..in den meisten Fällen
3. Die Bucket-Sortierung ist sehr schnell, verbraucht aber auch viel Platz. Es ist im Grunde der platzraubendste Sortieralgorithmus.

Ergänzung: Im Suchalgorithmus ist die beste Zeitkomplexität des vergleichsbasierten Suchalgorithmus ebenfalls O(logN). Zum Beispiel binäre Suche, ausgeglichener Binärbaum, Rot-Schwarz-Baum usw. Die Hash-Tabelle weist jedoch eine Sucheffizienz auf linearem Niveau von O(C) auf (die Sucheffizienz erreicht O(1) ohne Konflikte). Also: Ist die Idee der Hash-Tabelle der Bucket-Sortierung ähnlich?

Tatsächlich stellt die Bucket-Sortierung besondere Anforderungen an die Datenbedingungen. Wenn das Array groß ist, werden offensichtlich Hunderte Millionen Buckets zugewiesen unmöglich. Daher hat die Bucket-Sortierung ihre Grenzen und eignet sich für Situationen, in denen die Menge der Elementwerte nicht groß ist.

【Verwandte Empfehlungen】

1. Besondere Empfehlung: Version „php Programmer Toolbox“ V0.1 herunterladen

2. Kostenloses Java-Video-Tutorial

2.Umfassende Analyse von Java-Annotationen

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Methode der Bucket-Sortierung des Java-Zahlenvervollständigungsalgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!