Detaillierte Erläuterung der Zusammenführungssortierung im PHP-Sortieralgorithmus series

Detaillierte Erläuterung der Zusammenführungssortierung im PHP-Sortieralgorithmus series_php skills

jacklove

Freigeben： 2023-04-02 10:18:01

Original

2161 Leute haben es durchsucht

Dieser Artikel stellt hauptsächlich die relevanten Informationen der PHP-Sortieralgorithmus-Reihe Merge Sort im Detail vor. Interessierte Freunde können sich auf

Merge Sort

Zusammenführungssortierung (MERGE-SORT) ist ein effektiver Sortieralgorithmus, der auf der Zusammenführungsoperation basiert. Dieser Algorithmus ist eine sehr typische Anwendung der Divide-and-Conquer-Methode (Pide and Conquer). 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 und die beiden geordneten Arrays zu vergleichen , je nachdem, welcher Wert kleiner ist, und fügen Sie das Element in das dritte Array ein. Nach der Aufnahme wird das Element im entsprechenden Array gelöscht usw. Wenn ein Array abgerufen wird und keine Elemente vorhanden sind, können Sie die restlichen Elemente hinzufügen das andere Array direkt zum dritten Array.

Prinzip

1. Füge alle zwei benachbarten Zahlen in der Sequenz zusammen, um ceil(n/2)-Sequenzen zu bilden. Nach dem Sortieren enthält jede Sequenz zwei Elemente, das letzte Die Sequenz darf nur ein Element haben.

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 Zusammenführung

(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 Fusion

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

PHP-Code-Implementierung

<?php
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);
}

Nach dem Login kopieren

Ich hoffe, dass es für das gesamte Studium hilfreich ist Jeder wird die chinesische PHP-Website unterstützen.

Artikel, die Sie interessieren könnten:

Detaillierte Erläuterung der Direktauswahl-Reihenfolge von PHP-Sortieralgorithmen

Detaillierte Erläuterung der Einfügungssortierung der PHP-Sortieralgorithmusreihe

Erklärung des in PHP implementierten Bucket-Sortieralgorithmus

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