1. Einführung in die Sortierung von Eimer
Die Bucket-Sortierung ist ein zählender Sortieralgorithmus. Das Arbeitsprinzip besteht darin, die Daten in eine begrenzte Anzahl von Eimer zu unterteilen, und dann wird jeder Eimer separat sortiert (es ist möglich, andere Sortieralgorithmen zu verwenden oder weiterhin auf wiederkehrende Weise zu sortieren). Wenn die zu sortierenden Werte in den Daten gleichmäßig verteilt sind, beträgt die Komplexität der Bucket -Sortierzeit θ (n). Die Sortierung des Eimers unterscheidet sich von der schnellen Sortierung, es ist keine Vergleichssortierung und wird nicht durch die geringere Zeitkomplexität O (NLOGN) beeinflusst.
In den folgenden 4 Schritten wird die Sortierung der Eimer -Sortierung durchgeführt:
(1) Stellen Sie eine feste Anzahl leerer Eimer ein.
(2) Legen Sie die Daten in den entsprechenden Eimer.
(3) Sortieren Sie die Daten in jedem nicht leeren Eimer.
(4) Spleißen Sie die Daten aus dem nicht leeren Eimer, um das Ergebnis zu erzielen.
Die Sortierung von Eimern ist hauptsächlich für Integer-Daten im kleinen Bereich geeignet und ist unabhängig und gleichmäßig verteilt. Die Datenmenge, die berechnet werden können, ist groß und erfüllt die lineare erwartete Zeit.
2. Demonstration des Bucket Sorting Algorithmus
Zum Beispiel gibt es jetzt eine Reihe von Daten [7, 36, 65, 56, 33, 60, 110, 42, 42, 94, 59, 22, 83, 84, 63, 77, 67, 101]. Wie sortiere ich es von klein bis groß?
Betriebsschritte:
(1) Stellen Sie die Anzahl der Eimer auf 5 leere Eimer ein, ermitteln Sie den Maximalwert von 110 und den Mindestwert von 7, und der Bereich jedes Eimers beträgt 20,8 = (110-7+1)/5.
(2) Durchqueren Sie die Originaldaten und legen Sie sie mit einer verknüpften Listenstruktur in den entsprechenden Eimer. Die Zahl 7, der Bucket Index -Wert ist 0, die Berechnungsformel ist der Boden ((7 7) / 20,8), die Zahl 36, der Bucket -Indexwert 1, die Berechnungsformel Floor ((36 7) / 20,8).
(3) Wenn Sie zum zweiten Mal Daten in den Eimer mit demselben Index einfügen, bestimmen Sie die Größe der vorhandenen Zahlen und neu eingefügten Zahlen im Eimer und setzen Sie sie von links nach rechts von klein bis groß ein. Zum Beispiel: Wenn der Eimer mit Index 2 beim Einfügen von 63 eingefügt wird, befinden sich bereits 4 Zahlen 56, 59, 60 und 65 in den Eimer, und dann wird die Nummer 63 links von 65 eingefügt.
(4) Nicht leere Eimer verschmelzen, die Eimer 0, 1, 2, 3 und 4 in der Reihenfolge von links nach rechts verschmelzen.
(5) Holen Sie sich die Struktur der Eimer -Sortierung
3. Implementierung von NodeJS -Programm
Es ist nicht schwierig, reife Algorithmen wie die Sortierung von Eimer zu implementieren. Nach den obigen Ideen habe ich ein einfaches Programm geschrieben, um sie zu implementieren. Ich bin der Meinung, dass der problematischste Teil die Verwendung von JavaScript zur Manipulation der verknüpften Liste ist.
Der tatsächliche Code lautet wie folgt:
'verwenden strikt';//////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////// Sortieren ([1,4,1,5,3,2,3,3,2,5,2,8,9,2,1], 5) * Sortieren ([1,4,1,5,3,2,3,3,2,5,5,2,8,9,9,2,1], 5,0,5) */exports. count = count || (Graf> 1? Count: 10); // maximale und minimale Werte beurteilen var min = arr [0], max = arr [0]; für (var i = 1; i <arr.length; i ++) {min = min <arr [i]? min: arr [i]; max = max> arr [i]? Max: arr [i]; } var delta = (max - min + 1) / count; // console.log (min+","+max+","+delta); // Bucket var buckets initialisieren = []; // Speicherdaten zum Bucket für (var i = 0; i <arr.length; i ++) {var idx = math.floor ((arr [i] - min) /delta); // Bucket Index if (Buckets [idx]) {// Nicht-leerer Bucket var bucket = buckets [idx]; var Insert = false; // FLAGE STONE L.RETRAVERSAL (Bucket, Funktion (Element, Done) {if (arr [i] <= item.v) {// kleiner als, einfügen l.append (item, _val (arr [i])); if (! insert) {// größer als, l.Append (Bucket, _val (arr [i])); }} else {// leerer Bucket var bucket = l.init (); L.Append (Bucket, _val (arr [i])); Eimer [IDX] = Bucket; // Linklisten -Implementierung}} var result = []; für (var i = 0, j = 0; i <count; i ++) {l.retraversal (Buckets [i], Funktion (Element) {// console.log (i+":"+item.v); Ergebnis [j ++] = item.v;}); } Rückgabeergebnis;} // Linked List Storage -Objektfunktion _val (v) {return {v: v}}Führen Sie das Programm aus:
var algo = require ('./ index.js'); console.log (algo.bucketsort.sort (Daten, 10)); // 10 EimerAusgabe:
7, 22, 33, 36, 42, 42, 56, 67, 67, 77, 83, 84, 94, 101, 110. 63, 65, 67, 77, 83, 84, 94, 101, 110] [7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101] 84, 94, 101, 110 ][ 7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110 ][ 7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110
Was erklärt werden muss, ist:
(1) Sortieren im Eimer können während des Einfügungsverfahrens implementiert werden, wie im Programm beschrieben; Oder es kann ohne Sortierung eingefügt und dann während des Zusammenführungsvorgangs sortiert werden, und schnell sortiert werden.
(2) verlinkte Liste. In der zugrunde liegenden API des Knotens befindet sich eine Implementierung der verknüpften Liste. Ich habe es nicht direkt verwendet, sondern über das LinkList-Paket aufgerufen: https://github.com/nodejs/node-v0.x-archive/blob/master/lib/_linklist.js
V.
Eines der berühmtesten Anwendungsszenarien für die Sortierung von Eimer ist es, die Punktzahlen der College -Aufnahmeprüfung zu zählen. Die Zahl der Kandidaten für die Aufnahmeprüfung der National College in einem Jahr beträgt 9 Millionen, und die Punktzahlen sind Standard mit mindestens 200 und maximal 900. Es gibt keine Dezimalzahl. Wenn diese 9 Millionen Zahlen sortiert sind, was sollen wir dann tun?
Algorithmusanalyse:
(1) Wenn Sie eine vergleichsbasierte Sortierung und Schnellsortierung verwenden, lautet die durchschnittliche Zeitkomplexität O (NLogn) = O (9000000*log9000000) = 144114616 = 144 Millionen Vergleiche.
(2) Wenn Sie zählbasierte Sortierung, Eimersortierung und durchschnittliche Komplexität verwenden, können Sie die lineare Komplexität steuern. Bei der Erstellung von 700 Eimer, einem Eimer von 200 Minuten bis 900 Minuten, O (n) = O (90000000), entspricht es einmal 900 -W -Datenstücke.
Wir führen ein Programm aus, um die schnelle Sortier- und Eimer -Sortierung gleichzeitig zu vergleichen.
// Daten in [200.900] in [200.900] geschlossene Intervall var data = algo.data.randomdata (1000*1000.200.900); var s1 = neues Datum (). Buckets var S3 = neues Datum (). GetTime (); console.log ("Quicksort-Zeit: %SMS", S2-S1); Konsole.log ("Bucket Time: %SMS", S3-S2);Ausgabe:
Schnellsortzeit: 14768msbucket Zeit: 1089ms
Daher ist die Sortierung von Eimer -Sortierungen für den Fall einer Eintrittsprüfung der College -Aufnahme geeignet! Unsere Verwendung geeigneter Algorithmen in geeigneten Szenarien bringt Leistungsverbesserungen des Programms über die Hardware hinaus.
5. Bucket Sortierkostenanalyse
ABER...
Die Sortierung von Bucket verwendet die Kartierungsbeziehung von Funktionen und verringert fast alle Vergleichsarbeiten. Tatsächlich entspricht die Berechnung des F (k) -Wertwerts der Bucket -Sortierung der Teilung in der schnellen Reihenfolge und hat eine große Datenmenge in grundsätzlich geordnete Datenblöcke (Eimer) unterteilt. Dann müssen Sie nur erweiterte Vergleiche und Sortieren einer kleinen Datenmenge im Eimer durchführen.
Die zeitliche Komplexität der Bucket -Sortier -N -Schlüsselwörter ist in zwei Teile unterteilt:
(1) Schleifen, um die Bucket Mapping -Funktion jedes Schlüsselworts zu berechnen, und diese Zeit ist die Komplexität O (n).
(2) Verwenden Sie den erweiterten Vergleichssortierungsalgorithmus, um alle Daten in jedem Eimer mit einer zeitlichen Komplexität von ∑O (ni*logni) zu sortieren. Wo Ni die Datenmenge des I-Th-Eimers ist.
Offensichtlich ist Teil (2) die Determinante der Leistung der Eimersortierung. Das Minimieren der Datenmenge im Eimer ist die einzige Möglichkeit, die Effizienz zu verbessern (da die beste durchschnittliche Zeitkomplexität basierend auf der Vergleichssorierung nur O (N*logn) erreichen kann). Daher müssen wir unser Bestes geben, um die folgenden zwei Punkte zu machen:
(1) Die Mapping -Funktion f (k) kann n Daten gleichmäßig M -Daten zuweisen, so dass jeder Eimer [N/m] Datenvolumina aufweist.
(2) Versuchen Sie, die Anzahl der Fässer zu erhöhen. Im Extremfall kann jeder Eimer nur eine Daten abrufen, wodurch der Sortierbetrieb von Daten im Eimer vollständig vermieden wird. Natürlich ist es nicht einfach, dies zu tun. Wenn die Datenmenge enorm ist, macht die F (K) -Funktion die Anzahl der Bucket -Sammlungen riesig und der Raumabfall ist schwerwiegend. Dies ist ein Kompromiss zwischen Zeit- und Raumkosten.
Damit N -Daten sortiert sind und M -Eimer sind, lautet die durchschnittliche Komplexität der Bucket -Sortierzeit jedes Eimers [N/M] -Daten:
O (n)+o (m*(n/m)*log (n/m)) = o (n+n*(logn-logm)) = o (n+n*logn-n*logm)
Wenn n = m, dann, wenn nur ein Daten pro Eimer unter der Grenze vorhanden ist. Die beste Effizienz der Eimersortierung kann O (n) erreichen.
6. Zusammenfassung
Die durchschnittliche Zeitkomplexität der Eimersortierung ist linear O (N+C), wobei c = n*(logn-logm). Wenn die Anzahl der Fässer m im Verhältnis zum gleichen N größer ist, ist die Effizienz umso höher und die beste Zeitkomplexität O (N). Natürlich ist die Raumkomplexität der Eimersortierung o (n+m). Wenn die Eingabedaten sehr groß sind und die Anzahl der Eimer sehr groß ist, sind die Platzkosten zweifellos teuer. Darüber hinaus ist die Eimer -Sortierung stabil.
Tatsächlich habe ich ein anderes Gefühl: Unter den Suchalgorithmen ist die beste Zeitkomplexität des vergleichsbasierten Suchalgorithmus O (logn). Zum Beispiel halbfinische Suche, ausgewogene binäre Bäume, rote und schwarze Bäume usw. Die Hash-Tabelle hat jedoch eine lineare Suchwirkungsgrad von O (C) (die Suchseffizienz erreicht O (1) bei keinem Konflikt). Schauen wir uns gut an: Sind die Gedanken und die Eimer -Sortierung der Hash -Tische das gleiche Lied?