前奏
經過幾天的痛苦沉思，最終決定，把原程序員面試題狂想曲系列正式更名為程序員編程藝術系列，同時，狂想曲創作組更名為編程藝術室。之所以要改名，我們考慮到三點：1、為面試服務不能成為我們最終或最主要的目的，2、我更願把解答一道道面試題，ACM題等各類程序設計題目的過程，當做一種藝術來看待，3、藝術的提煉本身是一個非常非常艱難的過程，但我們樂意接受這個挑戰。
同時，本系列程序編程藝術-算法卷，大致分為三個部分：第一部分--程序設計，大凡如面試題目/ACM題目/poj的題目等各類程序設計的題，只要是好的，值得設計或深究的題目，我們都不拒絕。同時，緊扣實際，不斷尋找更高效的算法解決實際問題。第二部分--算法研究，主要以我個人此前寫的原創作品-十三個經典算法研究系列為題材，力爭通俗易懂，詳略得當的剖析各類經典的算法，並予以編程實現。第三部分--編碼素養，主要包括程序員編碼過程中一些編碼規范等各類及其需要注意的問題。
如果有可能的話，此TAOPP系列將采取TAOCP那樣的形式，出第一卷、第二卷、...。編程藝術來自哪裡?編程采取合適的數據結構?尋求更高效的算法?或者，好的編碼規范?希望，本TAOPP系列最終能給你一個完整的答復。
ok，如果任何人對本編程藝術系列有任何意見，或發現了本編程藝術系列任何問題，漏洞，bug，歡迎隨時提出，我們將虛心接受並感激不盡，以為他人創造更好的價值，更好的服務。
第一節、如何給磁盤文件排序
問題描述：
輸入：一個最多含有n個不重復的正整數的文件，其中每個數都小於等於n，且n=10^7。
輸出：得到按從小到大升序排列的包含所有輸入的整數的列表。
條件：最多有大約1MB的內存空間可用，但磁盤空間足夠。且要求運行時間在5分鐘以下，10秒為最佳結果。
分析：下面咱們來一步一步的解決這個問題，
1、歸並排序。你可能會想到把磁盤文件進行歸並排序，但題目要求你只有1MB的內存空間可用，所以，歸並排序這個方法不行。
2、位圖方案。熟悉位圖的朋友可能會想到用位圖來表示這個文件集合。例如正如編程珠玑一書上所述，用一個20位長的字符串來表示一個所有元素都小於20的簡單的非負整數集合，邊框用如下字符串來表示集合{1,2,3,5,8,13}：
0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0
上述集合中各數對應的位置則置1，沒有對應的數的位置則置0。
參考編程珠玑一書上的位圖方案，針對我們的10^7個數據量的磁盤文件排序問題，我們可以這麼考慮，由於每個7位十進制整數表示一個小於1000萬的整數。我們可以使用一個具有1000萬個位的字符串來表示這個文件，其中，當且僅當整數i在文件中存在時，第i位為1。采取這個位圖的方案是因為我們面對的這個問題的特殊性：1、輸入數據限制在相對較小的范圍內，2、數據沒有重復，3、其中的每條記錄都是單一的整數，沒有任何其它與之關聯的數據。
所以，此問題用位圖的方案分為以下三步進行解決：
第一步，將所有的位都置為0，從而將集合初始化為空。
第二步，通過讀入文件中的每個整數來建立集合，將每個對應的位都置為1。
第三步，檢驗每一位，如果該位為1，就輸出對應的整數。
經過以上三步後，產生有序的輸出文件。令n為位圖向量中的位數（本例中為1000 0000），程序可以用偽代碼表示如下：
view plaincopy to clipboardprint?
//磁盤文件排序位圖方案的偽代碼
//copyright@ Jon Bentley
//July、updated，2011.05.29。
//第一步，將所有的位都初始化為0
for i ={0,....n}
bit[i]=0;
//第二步，通過讀入文件中的每個整數來建立集合，將每個對應的位都置為1。
for each i in the input file
bit[i]=1;
//第三步，檢驗每一位，如果該位為1，就輸出對應的整數。
for i={0...n}
if bit[i]==1
write i on the output file
//磁盤文件排序位圖方案的偽代碼
//copyright@ Jon Bentley
//July、updated，2011.05.29。
//第一步，將所有的位都初始化為0
for i ={0,....n}
bit[i]=0;
//第二步，通過讀入文件中的每個整數來建立集合，將每個對應的位都置為1。
for each i in the input file
bit[i]=1;
//第三步，檢驗每一位，如果該位為1，就輸出對應的整數。
for i={0...n}
if bit[i]==1
write i on the output file
上面只是為了簡單介紹下位圖算法的偽代碼之抽象級描述。顯然，咱們面對的問題，可不是這麼簡單。下面，我們試著針對這個要分兩趟給磁盤文件排序的具體問題編寫完整代碼，如下。
view plaincopy to clipboardprint?
//copyright@ yansha
//July、2010.05.30。
//位圖方案解決10^7個數據量的文件的排序問題
//如果有重復的數據，那麼只能顯示其中一個 其他的將被忽略
#include <iostream>
#include <bitset>
#include <assert.h>
#include <time.h>
using namespace std;
const int max_each_scan = 5000000;
int main()
{
clock_t begin = clock();
bitset<max_each_scan> bit_map;
bit_map.reset();
// open the file with the unsorted data
FILE *fp_unsort_file = fopen("data.txt", "r");
assert(fp_unsort_file);
int num;
// the first time scan to sort the data between 0 - 4999999
while (fscanf(fp_unsort_file, "%d ", &num) != EOF)
{
if (num < max_each_scan)
bit_map.set(num, 1);
}
FILE *fp_sort_file = fopen("sort.txt", "w");
assert(fp_sort_file);
int i;
// write the sorted data into file
for (i = 0; i < max_each_scan; i++)
{
if (bit_map[i] == 1)
fprintf(fp_sort_file, "%d ", i);
}
// the second time scan to sort the data between 5000000 - 9999999
int result = fseek(fp_unsort_file, 0, SEEK_SET);
if (result)
cout << "fseek failed!" << endl;
else
{
bit_map.reset();
while (fscanf(fp_unsort_file, "%d ", &num) != EOF)
{
if (num >= max_each_scan && num < 10000000)
{
num -= max_each_scan;
bit_map.set(num, 1);
}
}
for (i = 0; i < max_each_scan; i++)
