Beispielanalyse für den PHP-Heap-Sortieralgorithmus

Dieses Mal werde ich Ihnen eine Beispielanalyse des PHP-Heap-Sortieralgorithmus bringen. Was sind die Vorsichtsmaßnahmen für die Beispielanalyse des PHP-Heap-Sortieralgorithmus? sehen.

Wie bereits erwähnt, wählt die einfache Auswahlsortierung den kleinsten Datensatz unter den n zu sortierenden Datensätzen aus und erfordert einen n-1-maligen Vergleich. Das ist verständlich Damit Daten so oft verglichen werden müssen, wie kann man sonst wissen, dass es sich um den kleinsten Datensatz handelt?

Leider speichert dieser Vorgang nicht die Vergleichsergebnisse der letzten Fahrt. Viele Vergleiche wurden bei der vorherigen Fahrt durchgeführt, aber aufgrund der vorherigen Fahrt waren diese Vergleichsergebnisse Da die Werte beim Sortieren nicht gespeichert wurden, wurden diese Vergleichsvorgänge beim nächsten Sortierdurchgang wiederholt, sodass eine größere Anzahl von Vergleichen aufgezeichnet wurde.

Wenn Sie jedes Mal den kleinsten Datensatz auswählen und basierend auf den Vergleichsergebnissen entsprechende Anpassungen an anderen Datensätzen vornehmen können, ist die Gesamteffizienz der Sortierung sehr hoch. Die Heap-Sortierung ist eine Verbesserung gegenüber der einfachen Auswahlsortierung, und die Auswirkung dieser Verbesserung ist sehr offensichtlich.

Grundidee:

Bevor wir die Heap-Sortierung einführen, stellen wir zunächst den Heap vor:

"Dahua-Datenstruktur" 》Definition in: Ein Heap ist ein vollständiger Binärbaum mit den folgenden Eigenschaften: Der Wert jedes Knotens ist größer oder gleich dem Wert seines linken und rechten untergeordneten Knotens und wird zu einem Big-Top-Heap (großer Root-Heap). Der Wert jedes Knotens ist kleiner oder gleich seinem Wert. Die Werte des linken und rechten Knotens werden zum kleinen oberen Heap (kleiner Root-Heap).

Als ich das sah, hatte ich auch Zweifel, ob der Heap ein vollständiger Binärbaum ist. Es gibt auch Leute im Internet, die sagen, dass es sich nicht um einen vollständigen Binärbaum handelt, aber egal, ob der Heap Da es sich um einen vollständigen Binärbaum handelt, behalte ich mir meine Meinung vor. Wir müssen nur wissen, dass wir hier einen großen Root-Heap (kleinen Root-Heap) in Form eines vollständigen Binärbaums verwenden, hauptsächlich um die Speicherung und Berechnung zu erleichtern (wir werden die Bequemlichkeit später sehen).

Heap-Sortieralgorithmus:

Heap-Sortierung ist eine Sortiermethode mithilfe eines Heaps (vorausgesetzt, es handelt sich um einen großen Root-Heap). Die Grundidee ist: Konstruieren Sie die zu sortierende Sequenz in einem großen Root-Heap. Zu diesem Zeitpunkt ist der Maximalwert der gesamten Sequenz der Wurzelknoten oben im Heap. Entfernen Sie es (tauschen Sie es tatsächlich mit dem letzten Element des Heap-Arrays aus, wobei das letzte Element den Maximalwert hat) und rekonstruieren Sie dann die verbleibenden n-1 Sequenzen in einem Heap, sodass Sie die n Elemente erhalten Der nächstkleinere Wert. Wenn Sie dies wiederholt ausführen, können Sie eine geordnete Reihenfolge erhalten.

Grundoperationen des großen Root-Heap-Sortieralgorithmus:

①Heap-Aufbau, der Heap-Aufbau ist ein ständiger Prozess Anpassen des Heaps: Beginnen Sie mit der Anpassung von len/2 bis zum ersten Knoten, wobei len die Anzahl der Elemente im Heap ist. Der Prozess zum Erstellen eines Heaps ist ein linearer Prozess. Der Prozess zum Anpassen des Heaps wird immer von len/2 auf 0 aufgerufen, was o(h1) + o(h2) ... + o(hlen/2) entspricht. wobei h die Tiefe des Knotens darstellt, len /2 die Anzahl der Knoten darstellt. Dies ist ein Summierungsprozess und das Ergebnis ist linear O(n).

②Anpassungsheap: Der Anpassungsheap wird beim Aufbau des Heaps und auch beim Heap-Sortierungsprozess verwendet. Die Idee besteht darin, Knoten i mit seinen untergeordneten Knoten links (i) und rechts (i) zu vergleichen und den größten (oder kleinsten) der drei auszuwählen, wenn der größte (kleinste) Wert nicht Knoten i, sondern einer seiner untergeordneten Knoten ist Dort interagiert der Knoten i mit dem Knoten und ruft dann den Heap-Anpassungsprozess auf. Dies ist ein rekursiver Prozess. Die zeitliche Komplexität des Prozesses zum Anpassen des Heaps hängt von der Tiefe des Heaps ab. Es handelt sich um einen Vorgang von lgn, da er entlang der Tiefenrichtung angepasst wird.

③Heap-Sortierung: Die Heap-Sortierung wird mithilfe der beiden oben genannten Prozesse durchgeführt. Die erste besteht darin, einen Heap basierend auf Elementen zu erstellen. Nehmen Sie dann den Wurzelknoten des Heaps heraus (normalerweise tauschen Sie ihn gegen den letzten Knoten aus), setzen Sie den Heap-Anpassungsprozess mit den ersten Len-1-Knoten fort und nehmen Sie dann den Wurzelknoten heraus, bis alle Knoten entfernt wurden. Die zeitliche Komplexität des Heap-Sortierprozesses beträgt O(nlgn). Da die Zeitkomplexität beim Erstellen eines Heaps O (n) beträgt (ein Aufruf); die Zeitkomplexität beim Anpassen des Heaps beträgt lgn und wird n-1-mal aufgerufen, sodass die Zeitkomplexität der Heap-Sortierung O (nlgn) beträgt.

Um diesen Prozess klar zu verstehen, sind viele Diagramme erforderlich, aber ich bin faul. . . . . .

Algorithmusimplementierung:

<?php
//堆排序（对简单选择排序的改进）
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//调整 $arr[$start]的关键字，使$arr[$start]、$arr[$start+1]、、、$arr[$end]成为一个大根堆（根节点最大的完全二叉树）
//注意这里节点 s 的左右孩子是 2*s + 1 和 2*s+2 （数组开始下标为 0 时）
function HeapAdjust(array &$arr,$start,$end){
  $temp = $arr[$start];
  //沿关键字较大的孩子节点向下筛选
  //左右孩子计算（我这里数组开始下标识 0）
  //左孩子2 * $start + 1，右孩子2 * $start + 2
  for($j = 2 * $start + 1;$j <= $end;$j = 2 * $j + 1){
    if($j != $end && $arr[$j] < $arr[$j + 1]){
      $j ++; //转化为右孩子
    }
    if($temp >= $arr[$j]){
      break; //已经满足大根堆
    }
    //将根节点设置为子节点的较大值
    $arr[$start] = $arr[$j];
    //继续往下
    $start = $j;
  }
  $arr[$start] = $temp;
}
function HeapSort(array &$arr){
  $count = count($arr);
  //先将数组构造成大根堆（由于是完全二叉树，所以这里用floor($count/2)-1，下标小于或等于这数的节点都是有孩子的节点)
  for($i = floor($count / 2) - 1;$i >= 0;$i --){
    HeapAdjust($arr,$i,$count);
  }
  for($i = $count - 1;$i >= 0;$i --){
    //将堆顶元素与最后一个元素交换，获取到最大元素（交换后的最后一个元素），将最大元素放到数组末尾
    swap($arr,0,$i);
    //经过交换，将最后一个元素（最大元素）脱离大根堆，并将未经排序的新树($arr[0...$i-1])重新调整为大根堆
    HeapAdjust($arr,0,$i - 1);
  }
}
$arr = array(9,1,5,8,3,7,4,6,2);
HeapSort($arr);
var_dump($arr);

Laufendes Ergebnis:

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)
}

时间复杂度分析：

它的运行时间只要是消耗在初始构建对和在重建堆屎的反复筛选上。

总体上来说，堆排序的时间复杂度是 O(nlogn)。由于堆排序对原始记录的排序状态并不敏感，因此它无论是最好、最差和平均时间复杂度都是 O(nlogn)。这在性能上显然要远远好于冒泡、简单选择、直接插入的 O(n^2) 的时间复杂度了。

堆排序是一种不稳定排序方法。

相信看了本文案例你已经掌握了方法，更多精彩请关注php中文网其它相关文章！

推荐阅读：

PHP原型设计模式使用案例分析

PHP基数排序使用步骤详解

Das obige ist der detaillierte Inhalt vonBeispielanalyse für den PHP-Heap-Sortieralgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!