Detaillierte Erläuterung der Zusammenführungsart der PHP-Sortieralgorithmusserie

In diesem Artikel wird die Zusammenführungsart der PHP-Sortieralgorithmusreihe ausführlich erläutert.

Zusammenführungssortierung

Zusammenführungssortierung (MERGE-SORT) ist ein effektiver Sortieralgorithmus, der auf der Zusammenführungsoperation basiert. Dieser Algorithmus ist ein sehr effektiver Sortieralgorithmus, der die Divide-and-Conquer-Methode verwendet . Führen Sie die bereits geordneten Teilsequenzen zusammen, um eine vollständig geordnete Sequenz zu erhalten. Ordnen Sie also zuerst jede Teilsequenz und dann die Teilsequenzsegmente. Wenn zwei geordnete Listen zu einer geordneten Liste zusammengeführt werden, spricht man von einer bidirektionalen Zusammenführung.

Zusammenführungsprozess

Der Kern der Zusammenführungssortierung besteht darin, zwei geordnete Arrays zusammenzuführen. Angenommen, es gibt zwei geordnete Arrays. Welches ist kleiner? Nehmen Sie, wen Sie wollen, und fügen Sie das Element in das dritte Array ein. Nachdem Sie es genommen haben, wird das Element im entsprechenden Array gelöscht, und so weiter. Wenn Sie ein Array erhalten, das keine Elemente enthält, können Sie die restlichen Elemente des anderen hinzufügen Array. Elemente werden direkt zum dritten Array hinzugefügt.

Prinzip

1. Alle zwei benachbarten Zahlen in der Sequenz zusammenführen, um ceil(n/2)-Sequenzen zu bilden. Nach dem Sortieren enthält jede Sequenz zwei Elemente, und die letzte Sequenz kann nur vorhanden sein ein Element.

2. Führen Sie die obigen Sequenzen erneut zusammen, um ceil(n/4)-Sequenzen zu bilden, und die letzte Sequenz enthält möglicherweise nur drei oder weniger Elemente.

3. Wiederholen Sie Schritt 2, bis alle Elemente sortiert sind.

Beispiel

Sortieren Sie das Array [53,89,12,6,98,25,37,92,5]

Nach der ersten Zusammenführung

(53,89),12, (6,98),(25,37),(5,92)

Nach der zweiten Fusion

(12,53, 89), (6,25,37,98),(5,92)

Nach der dritten Fusion

(6,12,25,37,53,89,98) ,(5, 92)

Nach der vierten Zusammenführung

5,6,12,25,37,53,89,92,98

PHP-Code-Implementierung

function merge_sort($arr){
 
$length=count($arr);
 
if($length<=1){
 
return $arr;
 
}
 
//分解数组，递归排序
 
$half=ceil($length/2);
 
$arr2=array_chunk($arr,$half);
 
$left=merge_sort($arr2[0]);
 
$right=merge_sort($arr2[1]);
 
while(count($left)&&count($right)){
 
if($left[0]<$right[0]){
 
$reg[]=array_shift($left);
 
}else{
 
$reg[]=array_shift($right);
 
}
 
}
 
return array_merge($reg,$left,$right);
 
}

In diesem Artikel wird die Zusammenführungssortierung in der PHP-Sortieralgorithmus-Reihe ausführlich erläutert. Weitere Informationen finden Sie auf der chinesischen PHP-Website.

Verwandte Empfehlungen:

thinkPHP5-Framework-Datenbankkohärenter Betrieb: Cache()-Nutzungsdetails

Mehrfachvererbung und Tarits der PHP-Schnittstelle Tutorial-Details zum Erzielen mehrerer Vererbungseffekte

PHP-Tutorial zum Ermitteln des Start- und Enddatums der Woche eines bestimmten Jahres

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Zusammenführungsart der PHP-Sortieralgorithmusserie. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!