準確的問題描述和適合問題數據的演算法選擇

對磁碟文件進行排序，文件包含最多一千萬條記錄，每條記錄都是7位的整數，無其他相關數據，每個整數只出現一次，由於某種系統需要，只能提供1MB左右記憶體。由於是實時系統，最多運行幾分鐘就能給出回應，十秒鐘是比較理想的運行時間。

準確的問題描述：

輸入：一個包含n個正整數的文件，每個數都小於n，其中n=10 000 000。如果在輸入文件中出現兩個相同的整數就是致命錯誤。沒有其他數據與該整數相關。

輸出：按照升序輸出的文件

約束：大約有1MB的記憶體空間可用，有充足的的磁碟空間，運行時間達到十秒以內不需要優化。

可以利用bit向量來表示整數集合，例如8bit長的維向量{0,0,1,1,0,1,0,1}，可以表示1-8的整數集合{3,4,6,8}

因此

1、初始化bit向量為全0　　2、讀取磁碟數據i，並賦值bit[i] = 1　　3、掃描bit向量，if ( bit[i] == 1) print i

可行性：1MB = 1024 x 1024 x 8bit = 8388608bit，在大概1.25MB的條件下，就能夠將所有數據採用bit向量完成表示

 1 #include <stdio.h>
 2 #define arrSpace 262144
 3 int arr[arrSpace];
 4 char fileName[20];
 5 
 6 void init(){
 7     int i;
 8     for(i=0; i < arrSpace; i++){
 9         arr[i] = 0;
10     }
11 }
12 
13 int main(void){
14     int n;
15     int i,j;
16     
17     scanf("%s",fileName);
18     FILE *in = fopen(fileName,"r");
19     FILE *out = fopen("outSort.txt","w");
20     
21     while(fscanf(in, "%d", &n) != EOF){
22         arr[n/32] = arr[n/32] | (1<<(n%32));
23     }
24 
25     for(i=0; i<arrSpace; i++){
26         for(j=0; j<32; j++){
27             if((arr[i] & (1<<j)) != 0){
28                 fprintf(out,"%d\n",i * 32 + j);       
29             }
30         }
31     }
32    
33    fclose(in);
34    fclose(out);
35 }

c語言中int類型占據32bit，因此262144長度的int數組為1MB

通過對讀取的數據i對32求商和求餘的運算，例如60/32=1，60%32=28，則應該把數組arr[1]的第28個bit置位1（一個int為0-31bit）

因此將整數1(int型)左移28位並與arr[1]進行邏輯或運算，可以將對應的bit置1

在最後輸出的時候將1左移0-31位，並與arr做邏輯與運算如果結果為1，則說明數據中存在這個整數，將數據按照遍歷順序輸出到文件就完成任務。