Ich verstehe die Bedeutung der an Ort und Stelle Eigenschaft eines Sortieralgorithmus.Welche Bedeutung hat die `Stabilität` im Sortieralgorithmus?
Ich weiß, dass Stabilität bei der Aufrechterhaltung der relativen Ordnung hilft, aber beeinflusst die Stabilitätseigenschaft des Algorithmus seine Leistung?
Aus Wikipedia:
Ein Sortieralgorithmus stabil ist, wenn immer dann, wenn es zwei Datensätze R und S mit dem gleichen Schlüssel ist, und R erscheint, bevor S in der ursprünglichen Liste, dann R erscheint immer vor S in der sortierten Liste.
Über Ihre Fragen:
die Stabilität Eigenschaft des Algorithmus Beeinflusst es ist Leistung?
Ich denke, die Stabilität eines Algorithmus hängt nicht von ihrer Effizienz, sind zwei getrennte Konzepte.
Stabilität ist eine Eigenschaft, die ein Sortieralgorithmus je nach Art haben oder nicht haben kann, aber wie ein "Nebeneffekt" wirkt sich nicht direkt auf seine Leistung aus.
Ein instabiler Algorithmus kann leicht in stable konvertiert werden, indem ein zusätzlicher Indexschlüssel hinzugefügt wird, um zu vergleichen, ob die Primärschlüssel übereinstimmen.
Wenn Ihre Frage wie Wie implementieren Sie eine stabile Sortieralgorithmus, dann wird Stabilität wahrscheinlich Auswirkungen, da es eine zusätzliche Anforderung zu erfüllen ist.
Warum ist es notwendig?
Sie können über die Vorteile von stabilen Algorithmus in diesem question lesen.
Gibt es diese Frage: http://programmers.stackexchange.com/questions/247440/what-does-it-mean-for-a-sorting-algorithm-to-be-stable hilft Ihnen? Ich verstehe nicht ganz, was Sie hier fragen: Suchen Sie einfach nach einer Definition von "stabil"? –
Es ist notwendig, wenn der Anrufcode es will. I.e. es ist eine Frage der spezifischen Anwendung. Mit anderen Worten, es liegt an Ihnen: Wenn Sie stabile Sortierung für Ihre Zwecke benötigen, verwenden Sie stabile Sortierung. – AnT
Sortieralgorithmen müssen nicht stabil sein. Aber Sie als Benutzer möchten wissen, ob es stabil ist oder nicht (wenn Sie sich auf diese Eigenschaft verlassen). –