PHP-Sortieralgorithmus-Serie Bucket-Sortierung detaillierte Erklärung_php-Fähigkeiten

Dieser Artikel stellt allen die Bucket-Sortierung der PHP-Sortieralgorithmus-Reihe im Detail vor. Interessierte Freunde können darauf verweisen.

Bucket-Sortierung

Bucket-Sortierung oder sogenannte Box-Sortierung ist ein Sortieralgorithmus, der durch die Aufteilung von Arrays in eine begrenzte Anzahl von Buckets funktioniert. 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 nacheinander in die 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]

Bereiten Sie 10 leere Eimer vor, maximal Mehrere leere Buckets
[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)

1. Nehmen Sie die Zahlen aus dem zu sortierenden Array heraus und legen Sie dann 6 in den Bucket Nr. 6. Der Vorgang ähnelt diesem: Leerer Bucket [zu sortierendes Array [ 0 ] ] = zu sortierendes Array [ 0 ]

[6 2 4 1 5 9] Zu sortierendes Array
[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)

2. Nehmen Sie nacheinander die nächste Nummer aus dem zu sortierenden Array heraus, 2 wird herausgenommen und in Eimer Nr. 2 gelegt, egal welche Nummer es ist

[6 2 4 1 5 9] Zu sortierendes Array
[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)

3, 4, 5, 6 werden weggelassen, der Prozess ist das Gleiche, nachdem alle in den Eimer gelegt wurden, sieht es so aus:

[6 2 4 1 5 9] Zu sortierendes Array
[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;
}

Verwandte Empfehlungen:

Berechnung des Eisprungzeitraums Methode Überprüfung und Zusammenfassung des PHP-Sortieralgorithmus

Überprüfung und Zusammenfassung des PHP-Sortieralgorithmus_PHP-Tutorial

PHP-Sortieralgorithmus?Klassischer PHP-Sortieralgorithmus_PHP-Tutorial

Das obige ist der detaillierte Inhalt vonPHP-Sortieralgorithmus-Serie Bucket-Sortierung detaillierte Erklärung_php-Fähigkeiten. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!