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