PHP-Sortieralgorithmus Merging Sort (Merging Sort)

In diesem Artikel wird hauptsächlich der Merging Sort des PHP-Sortieralgorithmus vorgestellt. Er analysiert die Prinzipien, Definitionen, Verwendungsmethoden und zugehörigen Vorsichtsmaßnahmen für den Betrieb von PHP Merging Sort im Detail und zeigt Beispiele.

Das Beispiel in diesem Artikel beschreibt den Merging Sort des PHP-Sortieralgorithmus. Teilen Sie es wie folgt mit allen als Referenz:

Grundidee:

Zusammenführungssortierung: Es wird unter Verwendung der Idee von implementiert Zusammenführen (Zusammenführen) Sortiermethode. 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 zuerst das zu sortierende Intervall [s, t] in der Mitte, sortieren Sie dann den linken Teilbereich, 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 ist wie folgt:

Schritt 1: Beantragen Sie Speicherplatz, sodass seine Größe der Summe der beiden sortierten Sequenzen entspricht. Dieser Speicherplatz 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 die Teilung des Arrays in zwei Hälften und dann halbieren (bis die Teilsequenzlänge 1 ist) und dann die Teilsequenzen zusammenführen. 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 abgeschlossen. Versuchen wir es mit dem Aufruf:

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

Laufergebnis:

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 davon, ob die ursprüngliche Sequenz geordnet ist oder nicht, gruppiert und vergleicht, ist die beste, schlechteste und durchschnittliche Zeit die Komplexität alle

O(nlogn).

Der Zusammenführungsalgorithmus ist ein stabiler Sortieralgorithmus.

Auf diesen Artikel wird von „Dahua Data Structure“ verwiesen. Er wird hier nur zum späteren Nachschlagen aufgezeichnet.

Verwandte Empfehlungen:

PHP-Sortieralgorithmus Bubble Sort (Bubble Sort)

PHP-Sortieralgorithmus Simple Selection Sort (Simple Selection Sort)

PHP-Sortieralgorithmus Straight Insertion Sort (Straight Insertion Sort)

Das obige ist der detaillierte Inhalt vonPHP-Sortieralgorithmus Merging Sort (Merging Sort). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!