Heim > Artikel > Backend-Entwicklung > 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
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!