外部排序與k路合併與快速排序

哪一個更好？說1GB內存和100GB文件進行排序。外部排序與k路合併與快速排序

的10路合併需要一個實例： - 100 1GB負載，隨後用10個* 10 + 10 * 100 100MB負載（10路，隨後用10路合併）

快速排序需要100 * 7 * 2（nlogn）1GB負載？

2010-09-16 snk

快速排序意味着沒有一種'批量加載大小'（這與n-way合併排序相反）。也許你可以改進這個問題。 – 2010-09-16 19:47:22

你能詳細說說嗎？你的意思是快速排序不會保證像合併排序一樣的固定數量的負載？ – snk 2010-09-16 20:05:01

合併排序在處理大數據時更有效率。

的原因是因爲快速排序是，這意味着你必須先處理100GB頂底的做法，，比50GB的過程* 2 ... 就不可能適應整個數據到內存中，當你有大數據。

以其他方式，合併排序是一種自下而上的方法，正如您所描述的那樣，您可以將數據分成可以放入內存的小批量，並將它們合併到緩衝區中。

2011-03-21 23:50:28 Jimchao

quicksort有一個很有名的版本，這意味着你不需要在內存中放置超過2個元素 – user804649 2015-03-03 16:29:53

主要瓶頸實際上是讀取和寫入硬盤驅動器。我們從硬盤讀取每個元素兩次，並從硬盤寫入兩個元素。一次用於對塊進行排序，然後每次再進行一次用於多路合併。

相比之下，快速排序將在平均O（log n）次時讀/寫每個元素到硬盤。

2015-03-03 16:37:04 user804649

回答