Detaillierte Erläuterung der Merge-Sortierung des PHP-Sortieralgorithmus

Es gibt viele Arten von PHP-Sortieralgorithmen. In diesem Artikel werden hauptsächlich die relevanten Informationen zur Merge-Sortierung der PHP-Sortieralgorithmen vorgestellt. Ich hoffe, dass sie jedem helfen können.

Zusammenführungssortierung

Zusammenführungssortierung (MERGE-SORT) ist ein effektiver Sortieralgorithmus, der auf Zusammenführungsoperationen basiert. Der Algorithmus verwendet die Divide-and-Conquer-Methode (Pide and Conquer). eine sehr typische Anwendung. 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. Jede Sequenz enthält vier Elemente 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);
}

Haben Sie es schon gelernt? Jeder, bitte probiert es schnell.

Verwandte Empfehlungen:

Detaillierte Erläuterung der Bucket-Sortierung im PHP-Sortieralgorithmus series_php skills

Lernen Sie mehr über gängige PHP-Sortieralgorithmen

Beispielanalyse grundlegender, häufig verwendeter Sortieralgorithmen in JavaScript

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