PHP-Sortieralgorithmus Shell Sort (Shell Sort)

In diesem Artikel wird hauptsächlich der PHP-Sortieralgorithmus Shell Sort vorgestellt. Er analysiert detailliert die Prinzipien, Implementierungsmethoden und zugehörigen Vorsichtsmaßnahmen in Form von Beispielen.

Das Beispiel In diesem Artikel wird der PHP-Sortieralgorithmus Shell Sort beschrieben. Geben Sie es als Referenz an alle weiter. Die Details lauten wie folgt:

Grundidee:

Hill-Sortierung bedeutet, dass Datensätze nach a gruppiert werden Bei einer bestimmten Inkrementierung wird für jede Gruppe eine direkte Einfügungssortierung verwendet, und jede Gruppe enthält immer mehr Schlüsselwörter. Wenn die Inkrementierung auf 1 abnimmt, wird die gesamte Sequenz in eine Gruppe unterteilt und der Algorithmus beendet.

Operationsschritte:

Nehmen Sie zunächst eine Ganzzahl d1 kleiner als n (die Anzahl der Sequenzdatensätze) als erstes Inkrement und addieren Sie die Alle Datensätze werden gruppiert. Alle Datensätze, deren Abstand ein Vielfaches von d1 ist, werden in derselben Gruppe platziert. Führen Sie zuerst eine direkte Einfügungssortierung innerhalb jeder Gruppe durch, nehmen Sie dann das zweite Inkrement d2 < d1 und wiederholen Sie die obige Gruppierung und Sortierung, bis das Inkrement dt=1( dt < d(t-1) ...< d2 < d1), das heißt, bis alle Datensätze für die direkte Einfügungssortierung in derselben Gruppe platziert sind

Diese Methode ist im Wesentlichen eine gruppierte Einfügungsmethode

Vergleich Für Zahlen, die Da die Werte weit voneinander entfernt sind (Inkremente genannt), sodass sich die Zahlen über mehrere Elemente hinweg bewegen können, kann ein einzelner Vergleich[2] den Austausch mehrerer Elemente verhindern. D.L. Shell setzte diese Idee 1959 in einem nach ihm benannten Sortieralgorithmus um. Der Algorithmus unterteilt zunächst einen zu sortierenden Zahlensatz in mehrere Gruppen gemäß einem bestimmten Inkrement d, und die in jeder Gruppe aufgezeichneten Indizes unterscheiden sich um d. Sortiert alle Elemente in jeder Gruppe und verwendet dann ein kleineres Inkrement zum Sortieren. Innerhalb jeder Gruppe noch einmal sortieren. Wenn das Inkrement auf 1 sinkt, wird die gesamte zu sortierende Zahl in eine Gruppe aufgeteilt und die Sortierung ist abgeschlossen.

Im Allgemeinen wird die Hälfte der Sequenz zum ersten Mal als Inkrement genommen und dann jedes Mal halbiert, bis das Inkrement 1 beträgt.

Bezüglich der Methode zur Auswahl von Inkrementen heißt es, dass die beste Inkrementreihenfolge bisher nicht gefunden wurde, aber es besteht eine starke Anforderung, dass der letzte Inkrementwert gleich 1 sein muss.

Der Sortierprozess der Shell-Sortierung für eine bestimmte Instanz

Angenommen, die zu sortierende Datei enthält 10 Datensätze und die Schlüsselwörter lauten:

49, 38, 65, 97, 76, 13, 27, 49, 55, 04.

Die Werte der inkrementellen Sequenz sind:

5, 3, 1

Algorithmusimplementierung :

<?php
//希尔排序(对直接插入排序的改进)
function ShellSort(array &$arr)
{
  $count = count($arr);
  $inc = $count;  //增量
  do {
    //计算增量
    //$inc = floor($inc / 3) + 1;
    $inc = ceil($inc / 2);
    for ($i = $inc; $i < $count; $i++) {
      $temp = $arr[$i];  //设置哨兵
      //需将$temp插入有序增量子表
      for ($j = $i - $inc; $j >= 0 && $arr[$j + $inc] < $arr[$j]; $j -= $inc) {
        $arr[$j + $inc] = $arr[$j]; //记录后移
      }
      //插入
      $arr[$j + $inc] = $temp;
    }
    //增量为1时停止循环
  } while ($inc > 1);
}
//$arr = array(9,1,5,8,3,7,4,6,2);
$arr = array(49,38,65,97,76,13,27,49,55,04);
ShellSort($arr);
var_dump($arr);

Laufergebnisse:

array(10) {
 [0]=>
 int(4)
 [1]=>
 int(13)
 [2]=>
 int(27)
 [3]=>
 int(38)
 [4]=>
 int(49)
 [5]=>
 int(49)
 [6]=>
 int(55)
 [7]=>
 int(65)
 [8]=>
 int(76)
 [9]=>
 int(97)
}

Komplexitätsanalyse:

Durch die Analyse des obigen Codes glaube ich, dass jeder ein gewisses Verständnis dafür hat, dass der Schlüssel zur Hill-Sortierung nicht darin besteht, sie zufällig zu gruppieren und Sortieren Sie sie einzeln, aber Datensätze, die durch ein bestimmtes „Inkrement“ getrennt sind, werden zu einer Teilsequenz geformt, um eine sprungartige Bewegung zu erreichen, was die Effizienz der Sortierung verbessert.

Die Zeitkomplexität im schlimmsten Fall ist O(n^2).

Hill-Sortierung ist eine instabile Sortierung.

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

Verwandte Empfehlungen:

PHP-Sortieralgorithmus, Serien-Einfügesortierung, Beispielfreigabe

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