Ist die Heap-Sortierung stabil?

Heap-Sortierung, Schnellsortierung, Hill-Sortierung und Direktauswahlsortierung sind instabile Sortieralgorithmen, während Radix-Sortierung, Blasensortierung, Direkteinfügungssortierung, Halbeinfügungssortierung und Zusammenführungssortierung dies sind ein stabiler Sortieralgorithmus.

Heap-Sortierung

Wir wissen, dass die Struktur des Heaps darin besteht, dass die untergeordneten Knoten des Knotens i 2*i- und 2*i+1-Knoten sind. Ein großer oberer Heap erfordert den übergeordneten Knoten ist größer oder gleich seinen 2 untergeordneten Knoten. Ein kleiner oberer Heap erfordert, dass der übergeordnete Knoten größer oder gleich seinen 2 untergeordneten Knoten ist.

In einer Sequenz der Länge n besteht der Prozess der Heap-Sortierung darin, den größten (Big Top Heap) oder den Kleinsten (Small Top Heap) auszuwählen, beginnend mit dem n/2ten und seinen untergeordneten Knoten mit einer Gesamtsumme von 3 Werte. Die Wahl zwischen Elementen zerstört sicherlich nicht die Stabilität. Wenn jedoch Elemente für n/2-1, n/2-2, ...1 übergeordnete Knoten ausgewählt werden, wird die Stabilität zerstört.

Es ist möglich, dass der n/2-te Elternknoten das nächste Element austauscht und der n/2-te Elternknoten nicht das nächste gleiche Element austauscht. Dann wird die Stabilität zwischen diesen beiden gleichen Elementen zerstört. Daher ist die Heap-Sortierung kein stabiler Sortieralgorithmus.

Das obige ist der detaillierte Inhalt vonIst die Heap-Sortierung stabil?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!