Heim >Backend-Entwicklung >PHP-Tutorial >Detaillierte Erläuterung der Bucket-Sortierung in der PHP-Sortieralgorithmus-Reihe
Dieser Artikel stellt allen die Bucket-Sortierung der PHP-Sortieralgorithmus-Reihe im Detail vor. Interessierte Freunde können sich auf
Bucket-Sortierung
Bucket-Sortierung oder sogenannte Bin-Sortierung ist ein Sortieralgorithmus, der Arrays in eine begrenzte Anzahl von Buckets aufteilt. Jeder Bucket wird einzeln sortiert (es kann möglich sein, einen anderen Sortieralgorithmus 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 nicht durch die Untergrenze von O(n log n) beeinflusst.Prinzip
Legen Sie ein quantitatives Array als leeren Eimer fest. Durchsuchen Sie die Reihenfolge und legen Sie die Elemente einzeln in den entsprechenden Eimer.
Sortieren Sie jeden Eimer, der nicht leer ist.
Platzieren Sie Gegenstände aus dem Eimer, der nicht leer ist, wieder in der ursprünglichen Reihenfolge.
Beispiel
Angenommen, die zu sortierenden Zahlen [6 2 4 1 5 9][0 0 0 0 0 0 0 0 0 0] Leere Buckets
[0 1 2 3 4 5 6 7 8 9] Bucket-Nummer (existiert eigentlich nicht)
[0 0 0 0 0 0 6 0 0 0] Leerer Bucket
[0 1 2 3 4 5 6 7 8 9] Bucket-Nummer (existiert tatsächlich nicht)
[0 0 2 0 0 0 6 0 0 0] Leerer Eimer
[0 1 2 3 4 5 6 7 8 9] Eimernummer (existiert eigentlich nicht)
[0 1 2 0 4 5 6 0 0 9] Leerer Eimer
[0 1 2 3 4 5 6 7 8 9] Eimernummer (existiert eigentlich nicht)
0 bedeutet leerer Eimer, überspringen Sie ihn, nehmen Sie ihn einfach in der Reihenfolge heraus: 1 2 4 5 6 9
PHP-Code-Implementierung
<?php function bucket_sort($arr){ $result=[]; $length=count($arr); //入桶 for($i=0,$max=$arr[$i];$i<$length;$i++){ if ($max<$arr[$i]) { $max=$arr[$i]; } $bucket[$arr[$i]]=[]; array_push($bucket[$arr[$i]],$arr[$i]); } //出桶 for($i=0;$i<=$max;$i++){ if(!empty($bucket[$i])){ $l=count($bucket[$i]); for ($j=0; $j <$l ; $j++) { $result[]=$bucket[$i][$j]; } } } return $result; }
Das Obige ist der gesamte Inhalt dieses Artikels Ich hoffe auch, dass jeder die chinesische PHP-Website unterstützt. Artikel, die Sie interessieren könnten:
Detaillierte Erläuterung der Merge-Art des PHP-Sortieralgorithmus series_php skills
Detaillierte Erläuterung der Direktauswahlsortierung in der PHP-Sortieralgorithmusreihe
Detaillierte Erläuterung der Einfügungssortierung in der PHP-Sortieralgorithmusreihe
Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Bucket-Sortierung in der PHP-Sortieralgorithmus-Reihe. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!