【引言】
在數(shù)據結構的課程上，我們學習了不少的排序算法，冒泡，堆，快排，歸并等。但是這些排序方法有著共同的特點，那就是所有的操作都是在內存中完成的，算法過程中不需要IO，這就使得這樣的算法總體上速度比較快，但是也隨之出現(xiàn)了一個問題：當需要排序的數(shù)據量異常的大的時候，以上的算法就顯得力不從心了。這時候，你需要一種另外的排序算法，它的名字叫“外排序”。
通常的，設備的內存讀取速度要比外存讀取速度快得多（RAM的訪問速度大約是磁盤的25萬倍），但是內存的容量卻要比外存小很多，當所有的數(shù)據不能在內存中完全放下的時候，就需要使用到外排序。這是外排序的一個顯著特征。
【什么是外排序】
外排序其實是采用一種分治（Divide and conquer algorithm）的算法設計思想，將一個大問題劃分成相對獨立的若干個小問題，解決小問題，得到小問題的答案，然后合并小問題的答案，最終得到原始大問題的答案。
在這里，我們舉一個外排的典型例子，二路外部歸并排序，假設我們有一個大文件，里面是待排序的數(shù)據，一共N個，這些數(shù)據在內存中放不下。排序過程如下：
- 將該大文件分割成大小為m的文件（m小于可用內存大小）
- 將這些小文件依次讀入內存，在內存中采用任一種排序算法排序并輸出文件F1，F(xiàn)2….Fn。（其實可以和第一步合并，可以省一次IO）
- 分塊快讀取兩個已經排完序的文件Fi和Fi+1，由于兩個文件已經排完序，這里可以用歸并排序，將兩個文件排序完畢，并寫入文件。（這個過程就好比有兩隊人馬將其合并為一對一樣）
- 重復過程3，直到剩余文件數(shù)為1。
以上就是二路外部歸并排序的基本思路，毫無疑問，這種排序算法需要讀取外存（IO）次數(shù)為log(2,N/m)，這時候算法的性能瓶頸已經不在內存中排序的時間復雜度上，而是內外村交換數(shù)據IO的次數(shù)了。這里我補充一句，各種操作的性能差別：
讀取網絡 > 磁盤文件IO > 讀取數(shù)據庫 > 內存讀取
這個可謂是程序性能的黃金法則，各位在寫對性能要求比較高的程序時一定要考慮。
好，言歸正傳，二路歸并排序這個算法的性能時比較低的。因此就有了多路歸并排序算法，其IO的次數(shù)為log(b, N/m)，其中b為幾路歸并。這個可以參考以下地址：
http://zh.wikipedia.org/wiki/%E5%A4%96%E6%8E%92%E5%BA%8F
【實戰(zhàn)訓練】
淘寶不同用戶的瀏覽log有上千萬or億數(shù)據（有重復），統(tǒng)計其中有相同瀏覽愛好的用戶。
轉載請注明出處：http://diducoder.com/mass-data-topic-9-external-sort.html