Detaillierte Erläuterung der Schritte zur Implementierung des Merge-Sort-Algorithmus in PHP

Dieses Mal werde ich Ihnen die Schritte zur Implementierung des Zusammenführungssortierungsalgorithmus in PHP ausführlich erläutern. Was sind die Vorsichtsmaßnahmen für die Implementierung des Zusammenführungssortierungsalgorithmus in PHP? ein Blick.

Grundidee:

Zusammenführungssortierung: Es handelt sich um eine Sortiermethode, die unter Verwendung der Idee des Zusammenführens (Zusammenführens) implementiert wird. Sein Prinzip besteht darin, dass unter der Annahme, dass die Anfangssequenz n Elemente enthält, sie als n geordnete Teilsequenzen betrachtet werden kann, jede Teilsequenz eine Länge von 1 hat und dann paarweise zusammengeführt wird, um ⌈ n / 2⌉ zu erhalten (⌈ x ⌉ bedeutet nicht Das kleinste Ganzzahl kleiner als 2-Wege-Zusammenführungssortierung.

1. Der Prozess des Zusammenführens:

a[i] übernimmt den vorderen Teil des a-Arrays (bereits sortiert), a[j] übernimmt den letzten Teil des a-Array-Teils (bereits sortiert)

r-Array speichert das sortierte a-Array

vergleicht die Größen von a[i] und a[j], wenn a[i] ≤ a[ j ], kopieren Sie dann das Element a[i] in der ersten geordneten Liste nach r[k] und addieren Sie jeweils 1 zu i und k. Andernfalls kopieren Sie das Element a[j] in der zweiten geordneten Liste. Kopieren Sie es nach r[; k] und addiere jeweils 1 zu j und k. Dieser Zyklus wird fortgesetzt, bis eine der geordneten Listen abgerufen wird, und kopiert dann die verbleibenden Elemente in der anderen geordneten Liste vom Index k zum Element des Index t. Normalerweise verwenden wir Rekursion, um den Zusammenführungssortierungsalgorithmus zu implementieren. Teilen Sie zunächst das zu sortierende Intervall [s, t] in der Mitte, sortieren Sie dann den linken Teilbereich, sortieren Sie dann den rechten Teilbereich und führen Sie schließlich a aus Zusammenführungsvorgang für die linken und rechten Intervalle. In geordnete Intervalle [s,t] zusammenführen.

2. Zusammenführungsvorgang:

Der Zusammenführungsvorgang (Merge), auch Zusammenführungsalgorithmus genannt, bezieht sich auf die Methode zum Zusammenführen zweier aufeinanderfolgender Sequenzen zu einer sequentiellen Sequenz.

Wenn eine Sequenz {6, 202, 100, 301, 38, 8, 1 vorhanden ist🎜>

Anfangszustand: 6, 202, 100, 301, 38, 8, 1

Nach der ersten Zusammenführung: {6,202}, {100,301}, {8,38}, {1}, Anzahl der Vergleiche: 3;

Nach der zweiten Zusammenführung: {6,100,202,301}, {1 ,8,38}, Anzahl der Vergleiche: 4;

Nach der dritten Zusammenführung: {1,6,8,38,100,202,301}, Anzahl der Vergleiche: 4;

Die Gesamtzahl der Vergleiche ist: 3+4+4=11,;

Die umgekehrte Zahl ist 14;

3. Algorithmusbeschreibung:

Das Funktionsprinzip von Der Zusammenführungsvorgang läuft wie folgt ab:

Schritt 1: Beantragen Sie Platz, sodass seine Größe der Summe der beiden sortierten Sequenzen entspricht. Dieser Platz wird zum Speichern der zusammengeführten Sequenz verwendet

Schritt 2: Legen Sie zwei Zeiger fest. Die Anfangspositionen sind die Startpositionen der beiden sortierten Sequenzen.

Schritt 3: Vergleichen Sie die Elemente, auf die die beiden Zeiger zeigen, wählen Sie das relativ kleine Element aus, legen Sie es in den Zusammenführungsbereich und verschieben Sie es den Zeiger zur nächsten Position

Wiederholen Sie Schritt 3, bis ein Zeiger das Ende der Sequenz überschreitet

Kopieren Sie alle verbleibenden Elemente der anderen Sequenz direkt an das Ende der zusammengeführten Sequenz

Algorithmusimplementierung:

Schauen wir uns zunächst den Hauptfunktionsteil an:

//交换函数
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//归并算法总函数
function MergeSort(array &$arr){
  $start = 0;
  $end = count($arr) - 1;
  MSort($arr,$start,$end);
}

In der Gesamtfunktion haben wir nur eine MSort()-Funktion aufgerufen, da wir rekursive Aufrufe verwenden möchten, kapseln wir MSort().

Werfen wir einen Blick auf die Funktion

: MSort()

function MSort(array &$arr,$start,$end){
  //当子序列长度为1时，$start == $end，不用再分组
  if($start < $end){
    $mid = floor(($start + $end) / 2); //将 $arr 平分为 $arr[$start - $mid] 和 $arr[$mid+1 - $end]
    MSort($arr,$start,$mid);  //将 $arr[$start - $mid] 归并为有序的$arr[$start - $mid]
    MSort($arr,$mid + 1,$end);  //将 $arr[$mid+1 - $end] 归并为有序的 $arr[$mid+1 - $end]
    Merge($arr,$start,$mid,$end);    //将$arr[$start - $mid]部分和$arr[$mid+1 - $end]部分合并起来成为有序的$arr[$start - $end]
  }
}

Die obige Funktion

implementiert das Teilen des Arrays in zwei Hälften und dann wieder in zwei Hälften (bis die Länge der Teilsequenz 1 beträgt). ) und dann die Teilfolge Combined dividieren. MSort()

Jetzt ist unsere Zusammenführungsoperationsfunktion

:Merge()

//归并操作
function Merge(array &$arr,$start,$mid,$end){
  $i = $start;
  $j=$mid + 1;
  $k = $start;
  $temparr = array();
  while($i!=$mid+1 && $j!=$end+1)
  {
    if($arr[$i] >= $arr[$j]){
      $temparr[$k++] = $arr[$j++];
    }
    else{
      $temparr[$k++] = $arr[$i++];
    }
  }
  //将第一个子序列的剩余部分添加到已经排好序的 $temparr 数组中
  while($i != $mid+1){
    $temparr[$k++] = $arr[$i++];
  }
  //将第二个子序列的剩余部分添加到已经排好序的 $temparr 数组中
  while($j != $end+1){
    $temparr[$k++] = $arr[$j++];
  }
  for($i=$start; $i<=$end; $i++){
    $arr[$i] = $temparr[$i];
  }
}

An diesem Punkt ist unser Zusammenführungsalgorithmus fertig. Versuchen wir, Folgendes aufzurufen:

$arr = array(9,1,5,8,3,7,4,6,2);
MergeSort($arr);
var_dump($arr);

Laufergebnisse:

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

Komplexitätsanalyse:

Da der Zusammenführungsalgorithmus unabhängig vom Original ist Unabhängig davon, ob die Sequenz geordnet ist oder nicht, wird sie gruppiert und verglichen, sodass ihre beste, schlechteste und durchschnittliche Zeitkomplexität alle

O(nlogn) ist.

Der Zusammenführungsalgorithmus ist ein stabiler Sortieralgorithmus.

Ich glaube, dass Sie die Methode beherrschen, nachdem Sie den Fall in diesem Artikel gelesen haben. Weitere spannende Informationen finden Sie in anderen verwandten Artikeln auf der chinesischen PHP-Website!

Empfohlene Lektüre:

Detaillierte Erläuterung der Anwendungsfälle des PHP-Singleton-Modus

php+receivemail ermöglicht das Senden und Empfangen von E-Mails

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Schritte zur Implementierung des Merge-Sort-Algorithmus in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!