Heim > häufiges Problem > Hauptteil

Ist die Heap-Sortierung stabil?

Freigeben: 2020-05-08 15:19:41
Original
18839 Leute haben es durchsucht

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!

Verwandte Etiketten:
Quelle:php.cn
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage