Wie wir wissen, ist die Quicksort-Leistung im Durchschnitt O (n * log (n)), aber die Merge- und Heapsort-Leistung ist auch O (n * log (n)) im Durchschnitt. Die Frage ist also, warum Quicksort im Durchschnitt schneller ist.Warum ist Quicksort im Durchschnitt schneller als andere?
Worst Case für schnelle Sortierung ist eigentlich schlechter als Heapsort und Mergesort, aber Quicksort ist im Durchschnitt schneller.
Wie, warum, wird es einige Zeit dauern, zu erklären und somit werde ich beziehen sich auf Skiena, The algorithm design manual.
Ein Zitat, das die quicksort vs merge/Heapsort fasst zusammen:
Wenn mit Algorithmen der gleichen asymptotisch konfrontiert Komplexität, Implementierung Details und Systemquirks wie Cache-Performance und Speichergröße Mai gut als der entscheidende Faktor erweisen. Was wir sagen können, ist, dass Experimente zeigen, dass, wo ein richtig implementiert Quicksort gut implementiert ist, es in der Regel 2-3 mal schneller als Mergesort oder Heapsort ist. Der Hauptgrund ist, dass die Operationen in der innersten Schleife einfacher sind. Aber ich kann nicht mit dir streiten, wenn du mir nicht glaubst, wenn ich sage, Quicksort ist schneller. Es ist eine Frage, deren Lösung außerhalb der analytischen Werkzeuge liegt, die wir verwenden. Der beste Weg zu erzählen ist, sowohl Algorithmen und Experiment zu implementieren.
Typischerweise quicksort signifikant ist in der Praxis schneller als andere O (n log n) Algorithmen, weil seine innere Schleife kann effizient auf den meisten Architekturen implementiert werden, und in den meisten realen Welt Daten, ist es möglich, Design Entscheidungen, die die Wahrscheinlichkeit der quadratischen Zeit zu minimieren. Darüber hinaus neigt Quicksort zu ausgezeichnete Nutzung des Speichers Hierarchie, die perfekte Nutzung von virtuellen Speicher und verfügbaren Caches. Obwohl quicksort kein In-Place ist und verwendet Hilfsspeicher, ist es sehr gut geeignet für moderne Computer Architekturen.
Werfen Sie einen Blick auf comparison with other sorting algorithms auf der gleichen Seite.
Siehe auch Why is quicksort better than other sorting algorithms in practice? auf der CS-Site.
Wissen Sie, wie genau es "virtuellen Speicher und Cache nutzt"? Irgendein Beispiel? – Michael
Wenn Sie versuchen, in Bezug auf den Algorithmus selbst zu denken, kümmern Sie sich nicht um virtuellen Speicher und Cache. Algorithmen verlassen sich nicht auf Hardware. – DarthVader
Der Algorithmus durchquert sequentiell, was eine gute "Referenzlokalität" (http: //en.wikipedia.org/wiki/Locality_of_reference), wodurch Ihr Cache gut funktioniert (und somit die Arbeit beschleunigt) – ChristopheD
Timsort könnte eine better Option sein, wie es für die Art von Daten optimiert ist, die beim Sortieren im Allgemeinen in der Python-Sprache gesehen werden, wo Daten oft eingebettete "Läufe" vorsortierter Elemente enthalten. Es wurde kürzlich auch von Java übernommen.
+1 für die interessante Verbindung nach Timsort. –
Heapsort ist O (n * log (n)) im schlimmsten Fall - wahrscheinlich in jedem Fall. – phkahler