Die Heapsortierung ist in zwei Prozesse unterteilt:
1. Bauen Sie einen Stapel.
Der Haufen ist im Wesentlichen ein völlig binärer Baum und muss Folgendes erfüllen: Die Schlüsselwörter eines Nicht-Blattknotens im Baum sind nicht größer als (oder nicht weniger als) die Schlüsselwörter des Kindes (falls vorhanden) des Knotens.
Der Haufen ist unterteilt in: einen großen Wurzelhaufen und ein kleiner Wurzelhaufen. Die aufsteigende Reihenfolge wird verwendet, um einen großen Wurzelhaufen zu sortieren, und die absteigende Reihenfolge wird verwendet, um kleine Wurzelhaufen zu sortieren.
Wenn es sich um einen großen Wurzelhaufen handelt, wird der Knoten mit dem größten Wert durch Einstellen der Funktion an das Haufenwurzel eingestellt.
2. Speichern Sie das Heap -Root am Schwanz und rufen Sie die Einstellfunktion für die verbleibende Sequenz auf. Nachdem die Einstellung abgeschlossen ist, speichern Sie den maximalen Anhänger am Schwanz -1 (-1, -2, ..., -i) und passen Sie dann die verbleibende Sequenz ein und wiederholen Sie den Vorgang, bis die Sortierung abgeschlossen ist.
Die Codekopie lautet wie folgt:
// Passen Sie die Funktion an
Funktion Headadjust (Elemente, Pos, Len) {
// Speichern Sie den aktuellen Knotenwert
var SWAP = Elemente [pos];
// Suchen Sie den untergeordneten Knoten links vom aktuellen Knoten
var child = pos * 2 + 1;
// rekursiv bis es keine Kinder gibt
während (Kind <len) {
// Wenn der aktuelle Knoten einen untergeordneten Knoten rechts hat und der richtige untergeordnete Knoten größer ist, verwenden Sie den richtigen Kinderknoten
// Vergleiche mit dem aktuellen Knoten
if (Kind + 1 <len && Elements [Kind] <Elemente [Kind + 1]) {
Kind += 1;
}
// Vergleichen Sie den aktuellen Knoten mit dem größten untergeordneten Knoten.
// auf dem Kinderknoten
if (Elemente [pos] <Elemente [Kind]) {
Elemente [pos] = Elemente [Kind];
pos = Kind;
Kind = pos * 2 + 1;
}
anders{
brechen;
}
Elemente [pos] = Swap;
}
}
// Bauen Sie den Haufen
Funktion Buildheap (Elemente) {
// Beginnen Sie vom letzten Knoten mit dem untergeordneten Knoten, vergleichen Sie den Knoten mit seinem untergeordneten Knoten.
// Nach dem Austausch der größten Zahl mit diesem Knoten wird der gleiche Austauschprozess wiederum an den vorderen Knoten durchgeführt.
// Bis ein großer oberer Haufen gebaut ist (aufsteigende Bestellung ist groß, die absteigende Reihenfolge ist kleiner oben)
für (var i = elements.length/2; i> = 0; i-) {
Headadjust (Elemente, I, Elements.Length);
}
}
Funktionsart (Elemente) {
// Bauen Sie den Haufen
Buildheap (Elemente);
// sich vom Ende der Sequenz einstellen
für (var i = elements.length-1; i> 0; i-) {
// Die Oberseite des Stapels ist immer das größte Element, daher wird die Oberseite des Stapels und das Schwanzelement ausgetauscht.
// Das maximale Element wird am Ende gespeichert und beteiligt sich nicht an nachfolgenden Anpassungen
var SWAP = Elemente [i];
Elemente [i] = Elemente [0];
Elemente [0] = Swap;
// Anpassungen vornehmen, das maximale Element an die Oberseite des Haufens einstellen
Headadjust (Elemente, 0, i);
}
}
VAR -Elemente = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log ('vor:' + Elementen);
sortieren (Elemente);
console.log ('After:' + Elemente);
Effizienz:
Zeitkomplexität: Best: O (Nlog2n), Schlimmste: O (Nlog2n), Durchschnitt: O (Nlog2n).
Raumkomplexität: O (1).
Stabilität: instabil