PHP-Hill-Sorting-Fallanalyse

Dieses Mal werde ich Ihnen eine Fallanalyse der PHP-Hill-Sortierung vorstellen. Was sind die Vorsichtsmaßnahmen bei der Verwendung des PHP-Hill-Sortierungsfalls?

Grundidee:

Hill-Sortierung bedeutet, dass Datensätze nach einem bestimmten Inkrement des Index gruppiert werden, und zwar für jeden, den die Gruppen verwenden Wenn das Inkrement allmählich abnimmt, enthält jede Gruppe mehr und mehr Schlüsselwörter. Wenn das Inkrement auf 1 abnimmt, wird die gesamte Sequenz in eine Gruppe aufgeteilt und der Algorithmus wird beendet.

Operationsschritte:

Nehmen Sie zunächst eine

Ganzzahl d1, die kleiner als n (Anzahl der Sequenzdatensätze) ist der erste Gruppiert inkrementell alle Datensätze in der Datei. 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);</a></p>Laufende Ergebnisse: <p style="text-align: left;"></p>
<pre class="brush:php;toolbar:false">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:

Analyse durch den obigen Code Ich glaube, jeder hat ein gewisses Verständnis dafür, dass der Schlüssel zur Hill-Sortierung nicht darin besteht, sie nach dem Zufallsprinzip zu gruppieren und einzeln zu sortieren, sondern darin, eine Unterfolge von Datensätzen zu bilden, die durch ein bestimmtes „Inkrement“ getrennt sind, um eine sprungartige Bewegung zu erreichen, was die Effizienz der Sortierung verbessert .

Die Zeitkomplexität im schlimmsten Fall ist

O(n^2).

Hügelsortierung ist eine instabile Sortierung.

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

Andere verwandte Artikel!

Empfohlene Lektüre:

Detaillierte Erläuterung der Schritte zur Verwendung des PHP-Schnellsortierungsalgorithmus

Detaillierte Erläuterung der Schritte zur Generierung von Werbung Poster mit PHP

Das obige ist der detaillierte Inhalt vonPHP-Hill-Sorting-Fallanalyse. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!