Was ist Bucket-Sortierung?

Bucket-Sortierung ist ein Sortieralgorithmus. Das Arbeitsprinzip besteht darin, das Array in eine begrenzte Anzahl von Buckets zu unterteilen. Dies ist auch ein induktives Ergebnis der Schubladensortierung Bei gleichmäßiger Verteilung verwendet die Bucket-Sortierung lineare Zeit, aber die Bucket-Sortierung ist keine Vergleichssortierung und wird durch die Untergrenze „O(n log n)“ nicht beeinflusst.

Bucket-Sortierung

Wenn bekannt ist, dass der Wertebereich von N Schlüsselwörtern von 0 bis reicht Zwischen M-1 und M ist viel kleiner als N. Der Bucket-Sortieralgorithmus erstellt einen „Bucket“ für jeden Wert des Schlüsselworts, d Buckets und sammeln Sie sie dann in der Reihenfolge der Buckets, um sie auf natürliche Weise zu ordnen.

Einführung:

Bucket Sort oder sogenannte Box Sort ist ein Sortieralgorithmus. Das Arbeitsprinzip besteht darin Teilen Sie das Array in eine begrenzte Anzahl von Buckets auf. Jeder Bucket wird einzeln sortiert (es ist möglich, andere Sortieralgorithmen zu verwenden oder die Bucket-Sortierung weiterhin rekursiv zu verwenden). Die Bucket-Sortierung ist ein induktives Ergebnis der Pigeonhole-Sortierung. Die Bucket-Sortierung verwendet die lineare Zeit (Θ(n)), wenn die Werte im zu sortierenden Array gleichmäßig verteilt sind. Die Bucket-Sortierung ist jedoch keine Vergleichssortierung und wird von der Untergrenze O(n log n) nicht beeinflusst.

Definition

Annahme: Die Eingabe ist eine gleichmäßig verteilte reelle Zahl im Intervall [0, 1), die durch einen Zufallsprozess generiert wird. Teilen Sie das Intervall [0, 1) in n Unterintervalle (Buckets) gleicher Größe, wobei jeder Bucket die Größe 1/n hat: [0, 1/n), [1/n, 2/n), [2/n, 3/n),…,[k/n, (k+1)/n),…verteilen Sie n Eingabeelemente auf diese Buckets, sortieren Sie die Elemente in den Buckets und verbinden Sie die Buckets dann der Reihe nach mit der Eingabe 0 ≤A[ 1 ..n] <1 Hilfsarray B[0..n-1] ist ein Zeigerarray, das auf den Bucket (verknüpfte Liste) zeigt.

Das obige ist der detaillierte Inhalt vonWas ist Bucket-Sortierung?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!