Was ist der beste Weg, um eine teilweise geordnete Liste zu sortieren?

Am besten mit einem kleinen Beispiel illustriert.
In Anbetracht derWas ist der beste Weg, um eine teilweise geordnete Liste zu sortieren?

Beziehungen

A < B < C 
A < P < Q

Richtige Ausgänge

ABCPQ or APQBC or APBCQ ... etc.

Mit anderen Worten wären, ist jede Bestellung, in der gültigen die angegebenen Beziehungen halten.

Ich interessiere mich am meisten für die Lösung, die am einfachsten zu implementieren ist, aber das beste O (n) in Geschwindigkeit und Zeit ist auch interessant.

Quelle

2009-01-26 mike g

Fragen Sie nach einer Möglichkeit, zwei sortierte Listen zusammenzuführen? – Triptych

Nein, eine einzige anfänglich zufällig geordnete Liste –

Ich bekomme immer noch nicht die Frage, sorry. Was meinst du mit "zufällig bestellt"? Und wenn das Ergebnis sortiert werden sollte, warum haben Sie mehrere mögliche Ergebnisse (die für mich nicht wirklich sortiert sind)? Ist ein anderes längeres Beispiel möglich? – Kosi2801

Dies wird topological sorting genannt.

Der Standardalgorithmus besteht darin, ein minimales Element auszugeben, dann zu entfernen und zu wiederholen.

Quelle

2009-01-26 18:32:16 starblue

Mehrere Arten machen. Sortiere zuerst nach der ersten Regel, dann nach der zweiten und so weiter. Sollte funktionieren, es sei denn, Ihre Regeln enthalten Widersprüche. Sicher, einfach zu implementieren.

Quelle

2009-01-26 18:02:56 user54579

Es ist nur ein Beispiel - es gibt nicht nur 2 Regeln im Allgemeinen –

Ich bin mir nicht sicher, ob die Anzahl der Regeln ein Problem ist. Das Ergebnis wird immer noch korrekt sein. ein kleines Performance-Problem vielleicht. – user54579

und es ist wichtig, eine stabile Sorte zu sein –

Sie könnten make_heap, pop_heap in C++ wiederholt mit der entsprechenden Sequenz aufrufen.

Quelle

2009-01-26 18:55:46

Was ist der beste Weg, um eine teilweise geordnete Liste zu sortieren?

Antwort

Verwandte Themen