Was ist der Unterschied zwischen externer Sortierung und interner Sortierung? Ich sehe nicht, wie die Eingabedaten im RAM gespeichert werden können oder nicht, was mit dem Algorithmus zu tun hat.Was ist der Unterschied zwischen externer Sortierung und interner Sortierung?
Bei der internen Sortierung werden alle zu sortierenden Daten während der Sortierung ständig gespeichert. Bei der externen Sortierung werden Daten außerhalb des Speichers (wie auf der Festplatte) gespeichert und nur in kleinen Blöcken in den Speicher geladen. Die externe Sortierung wird normalerweise angewendet, wenn Daten nicht vollständig in den Speicher passen.
So in der internen Sortierung können Sie so etwas wie Shell-Sortierung tun - greifen Sie einfach auf Array-Elemente, die Sie wollen, in welchem Moment Sie wollen. Dies ist bei der externen Sortierung nicht möglich - das Array ist nicht vollständig im Speicher, so dass Sie nicht willkürlich auf ein beliebiges Element im Speicher zugreifen können, und der wahlfreie Zugriff auf die Festplatte ist normalerweise extrem langsam. Der externe Sortieralgorithmus muss mit dem Laden und Entladen von Datenstücken auf optimale Weise umgehen.
externer Speicher - Sie erhalten Teile der Daten gleichzeitig? – committedandroider
@committedandroider: Ja, weil Sie nicht alle Daten in den verfügbaren Speicher passen können. – sharptooth
http://en.wikipedia.org/wiki/External_sorting –
http://en.wikipedia.org/wiki/Internal_sort –
Wenn Sie den Unterschied zwischen In-Memory- oder Out-of-Memory-Sortierung nicht sehen können Sie haben nicht genug über die Sache nachgedacht. Ich schlage vor, Sie schreiben Programme, um beides zu tun. Sortiere zuerst eine Liste von ganzen Zahlen der Länge 100; Als nächstes sortiere eine Liste von Ganzzahlen, die zum Beispiel auf 4 TB laufen. –