Ich muss eine doppelt verknüpfte Liste mit etwas anderes als Insertion sortieren, die auch in einer besseren Zeit als O (n^2) läuft. Ich habe über einen Quicksort nachgedacht, hatte aber Probleme mit dem Verständnis des Algorithmus. Könnten Sie mich auf eine einfach zu verstehende Dokumentation hinweisen, die mir beim Einstieg helfen könnte?Implementieren eines Quicksort einer Linked List?
Ich würde eigentlich eine merge sort empfehlen. Es fühlt sich an, als ob es mit einer doppelt verketteten Liste mehr Sinn macht, und es hat eine Laufzeit von O (n log n). Grundsätzlich finden Sie die Mitte und teilen Sie die Liste in zwei Hälften, sortieren Sie jede Hälfte von selbst, und kombinieren Sie dann die beiden in linearer Zeit.
Es gibt einen Thread here, der eine ziemlich gute funktionierende Implementierung in C++ hat, die vielleicht nicht die einfachste für Sie zu lesen ist, wenn Sie Java lernen, aber kann ein guter Ausgangspunkt sein.
Es ist auch eine ausgezeichnete hohe Beschreibung des Algorithmus bei this site.
Wichtig ist, dass die * worst case * Laufzeit im Gegensatz zu Quicksort auch 'O (n * log n) 'ist. Außerdem ist es einfach zu implementieren :) –
[Video von Quicksort Visualisierung Hungerian Volkstanz mit] (http://www.youtube.com/watch?v=ywWBy6J5gz8). –
Können Sie es in eine andere Datenstruktur extrahieren, um es zu sortieren, oder müssen Sie es an Ort und Stelle sortieren? Das Extrahieren in ein Array, das schnelle Sortieren und das Zurücksetzen in die verknüpfte Liste sollte etwa 2n + nlogn sein, was immer noch weniger als n Quadrat ist. – captncraig
Nein, ich kann keine andere Datenstruktur zum Speichern der Knoten verwenden. –