【程式設計珠玑】第一章 開篇

【程式設計珠玑】第一章 開篇

一. 題目

      如何給磁盤檔案排序？

     問題描述：

     輸入：一個最多含有n個不重複的正整數（也就是說可能含有少于n個不重複正整數）的檔案，其中每個數都小于等于n，且    n=10^7。

     輸出：得到按從小到大升序排列的包含所有輸入的整數的清單。

     條件：最多有大約1MB的記憶體空間可用，但磁盤空間足夠。且要求運作時間在5分鐘以下，10秒為最佳結果。

二.分析

      1）基于磁盤的歸并排序（耗時間）

     2）每個号碼采用32位整數存儲的話，1MB大約可以存儲250 000 個号碼，需要讀取檔案40趟才能把全部整數排序。（耗時間）

     3）位圖法，采用一個1千萬位的字元串表示每個數，比如{0,2,3}表示為   1  0 1 1 0 0 0 0 。（說明：左邊第一位表示 0 第二位表示1 第三位表示 2 。如果有則表示為1，否則為0）周遊每一個整數，有則标記為1，否則标記為0。然後按順序輸出每個整數。這種方法實際需要1.25MB記憶體，如果可以友善弄到記憶體的話可以采用此種方法。

     4）假如嚴格限制為1MB，可以采用的政策：兩次周遊或者除去第一位為0或1的整數。

         解釋：考慮到沒有以數字0或1開頭的電話号碼，可以省略對這些數的操作。

         兩次周遊：對  1 ---4999 999之間的數排序，需要存儲空間為：5000 000/8 =625 000 位元組（8為一個位元組中的位數） 對 5000 000 -10000 000 之間的數排序。 如果需要采用k趟算法，方法類似。

三. 算法實作

#include <stdio.h>  

#include <stdlib.h>  

#define SHIFT 5  //表示位移量

#define MASK 0x1F  //掩碼

#define N 10000000  //表示有1000萬個數

int a[1 + N/32];  //使用整形數組來模拟定義1000萬個位的數組

void set(int i) {  a[i>>SHIFT] |=  (1<<(i & MASK)); } //設定位數組中的從0開始的第i位為1 

void clr(int i)  {   a[i>>SHIFT] &= ~(1<<(i & MASK)); }  //設定位數組中的從0開始的第i位為0

int  test(int i) { return a[i>>SHIFT] &   (1<<(i & MASK)); }  //取出從0開始的第i位的值，用于檢測

int main()  

{       

       int i = 0;  

        //int  top = 1 + N/BITSPERWORD;  

        //memset(a, 0, sizeof(a)*sizeof(int)); 

       for(i=0;i<N;i++)

           clr(i);

       while (scanf("%d", &i))   

        set(i);  

        for (i = 0; i < N; i++)            

          if (test(i))   

          printf("%d\n", i);  

         return 0;  

}  

四. 參考來源

    1.  http://blog.csdn.net/tianshuai11/article/details/7555563

    2.  http://blog.csdn.net/ju136/article/details/6832331

    3. 《程式設計珠玑》讀書筆記