Beeinflusst die Implementierung von Mergesort die Stabilität?MergeSort Implementierung Stabilität
Zum Beispiel, wenn wir Arrays verwenden, um Merge-Sort zu implementieren, ist das weniger stabil als eine verknüpfte Liste Implementierung von merge sort?
Die meisten Implementierungen von Top-Down- (rekursiv) und Bottom-Up- (iterativ) Implementierungen von merge sort für Arrays oder verknüpfte Listen sind stabil. Der Schlüsselfaktor liegt in der Zusammenführungsfunktion, solange die Zusammenführungsfunktion gleich "linke" Elemente vor "rechte" Elemente bewegt, wird sie stabil sein. Der Vergleich kann "left" Element < = "right" Element sein oder im Fall von C++ Standard-Bibliothek, die nur weniger als zum Vergleich verwendet, ist sein Vergleich "rechts" Element < "links" -Element, also das "linke" Element wird verschoben, wenn es < = "richtiges" Element ist.
Ein anderes mögliches Problem wäre mit einer hybriden Mischsortierung, die eine nicht stabile Sortiermethode für kleine Elementgruppen verwendet.
Im Allgemeinen sind Sortierungen, die benachbarte Elemente austauschen (wie Blasensortierung), normalerweise stabil, während Sortierungen, die nicht benachbarte Elemente austauschen (wie schnelle Sortierung), normalerweise nicht stabil sind.
Merge sort sollte stabil mit beiden sein. Ob Sie eine Liste oder ein Array verwenden, hängt mehr davon ab, wofür Sie es verwenden.
Eine Sortiermethode ist stabil, wenn sie die relative Reihenfolge der Elemente mit gleichen Schlüsseln in einem Array beibehält.
Sowohl Top Down als auch Bottom Up Implementierung sind stabile Ansätze. Es ist unabhängig von Array oder Linked List.
Ein Sortieralgorithmus ist stabil oder nicht. So etwas wie "weniger stabil" gibt es nicht. –