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]

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;
}

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!