Kann jemand erklären, was "stabil" und "instabil" in Bezug auf verschiedene Sortieralgorithmen bedeutet> Wie kann man feststellen, ob ein Algorithmus stabil ist oder nicht, und welche Anwendungen haben instabile Sortieralgorithmen (da sie instabil sind)?Was bedeutet "stabil" und "instabil" für verschiedene Sortieralgorithmen?
Wenn ein Sortieralgorithmus als "instabil" bezeichnet wird, bedeutet dies, dass für alle Elemente, die denselben Rang haben, nicht sichergestellt ist, dass die Reihenfolge der verknüpften Elemente bei aufeinanderfolgenden Sortierungen dieser Sammlung gleich bleibt. Bei einer "stabilen" Sortierung enden die verknüpften Einträge immer in der gleichen Reihenfolge, wenn sie sortiert werden.
Für ein Anwendungsbeispiel ist der schnelle Sortieralgorithmus nicht stabil. Dies würde beispielsweise für Sortiervorgänge nach Priorität funktionieren (wenn zwei Aktionen die gleiche Priorität haben, wäre es wahrscheinlich nicht wichtig, welche Elemente einer Verknüpfung zuerst ausgeführt werden).
Ein stabiler Sortieralgorithmus hingegen ist gut für Dinge wie eine Rangliste für ein Online-Spiel. Wenn Sie eine instabile Sortierung verwenden, z. B. nach Punkten sortieren, könnte ein Benutzer, der die sortierten Ergebnisse auf einer Webseite anzeigt, bei der Seitenaktualisierung andere Ergebnisse erhalten, und Vorgänge wie Paging-Ergebnisse würden nicht korrekt funktionieren.
bearbeitet, um einige Beispiele zu enthalten, warum der Unterschied von Bedeutung ist. –
Unbrauchbare Sortierungen ergeben normalerweise vorhersehbare Ergebnisse, dh sie geben bei gleichen Daten keine unterschiedlichen Antworten. So zeigen Seitenaktualisierungen nur dann eine andere Reihenfolge für Gleichheitszeichen an, wenn sich andere Werte ändern. Die Ursache der Instabilität liegt in der Verwendung von Bäumen oder einer ähnlichen Datenstruktur beim Organisieren der Daten. –
Es ist bemerkenswert, dass eine häufigere Verwendung von stabilen Sortierungen die Sortierung nach mehreren Schlüsseln ist. Wenn Sie zum Beispiel ein Array mit Objekten haben, die Personen repräsentieren, und Sie möchten, dass dieses nach Alter sortiert ist, mit Bindungen nach Namen (alphabetisch), dann können Sie zuerst nach Namen und dann nach Alter sortieren und eine stabile Sortierung haben es in dem Zustand, den du suchst. –
Eine stabile Sortierung behält die Reihenfolge identischer Elemente bei. Jede Art kann durch Anhängen des Zeilenindexes an den Schlüssel stabil gemacht werden. Unstable-Sortierungen, wie zum Beispiel Heap-Sortierung und schnelle Sortierung, haben diese Eigenschaft nicht inhärent, aber sie werden verwendet, weil sie schneller und einfacher zu codieren sind als stabile Sortierungen. Soweit ich weiß, gibt es keine anderen Gründe, instabile Sorten zu verwenden.
Gehen wir zum obigen Punkt, den Azron (unter Ihrem Punkt) gemacht hat, und dem Beispiel, das er genommen hat, bedeutet das Gittersortierung, die wir in Windows machen in einer der stabilen Art implementiert? Grid-Sortierung bedeutet, die Dateien im Ordner nach Datum und Typ zu sortieren. –
Sortierungen, die in Sachen Dateimanager und Excel gemacht wurden, sind stabil, sie verwenden entweder eine stabile Sortierung oder die stabilisierte Version einer der instabilen Sortierungen. –
Vielleicht wäre dies besser geeignet auf http://programmers.stackexchange.com/ –