输入：给定一个文件，里面最多含有n个不重复的正整数（也就是说可能含有少于n个不重复正整数），且其中每个数都小于等于n，n=10^7。

输出：得到按从小到大升序排列的包含所有输入的整数的列表。

条件：最多有大约1MB的内存空间可用，但磁盘空间足够。且要求运行时间在5分钟以下，10秒为最佳结果。分析：下面咱们来一步一步的解决这个问题，

    1、归并排序。你可能会想到把磁盘文件进行归并排序，但题目要求你只有1MB的内存空间可用，所以，归并排序这个方法不行。

    2、位图方案。熟悉位图的朋友可能会想到用位图来表示这个文件集合。例如正如编程珠玑一书上所述，用一个20位长的字符串来表示一个所有元素都小于20的简单的非负整数集合，边框用如下字符串来表示集合

（1）位图方法，原理很简单，但是，主要学习c语言中的文件打开关闭，同时一定注意fseek啊，啊，啊，

1 //位图方法，适用于无重复，有一定范围的排序 2 //从1到10^7个数排序 3 //500万是0.625M分成两次 4 #include 
     
       5 #include 
      
        6 #include 
       
         7 #include 
        
          8 using namespace std; 9 char * filepath="unsort.txt";10 char * filesort="sort.txt";11 #define max_each 500000012 #define size 1000000013 14 int num[size+1];15 void createrandom()16 {17      FILE *fp = fopen("unsort.txt", "w");  18     assert(fp);  19    int n;20     for ( n = 1; n <= size; n++)    21         //之前此处写成了n=0;n
         
           bit;44     bit.reset();45     FILE * unsort_file=fopen(filepath,"r");46     assert(unsort_file);47     int num;48     while(fscanf(unsort_file,"%d ",&num)!=EOF)49     {50         if(num<=max_each)51             bit.set(num,1);52 53     }54     FILE * sort_file=fopen(filesort,"w");55     assert(sort_file);56     for(int i=1;i<=max_each;i++)57         if(bit[i]==1)58             fprintf(sort_file,"%d ",i);59     bit.reset();60     int result = fseek(unsort_file, 0, SEEK_SET);  61     if (result)  62         cout << "fseek failed!" << endl;  63     while(fscanf(unsort_file,"%d ",&num)!=EOF)64     {65         if(num>max_each)66         {67             num-=max_each;68             bit.set(num,1);69         }70     }71     for(int i=1;i<=max_each;i++)72         if(bit[i]==1)73             fprintf(sort_file,"%d ",i+max_each);74     clock_t end=clock();75     cout<<"finish and usetime=  "<<(end-begin)/CLK_TCK<<"s"<
         
        
       
      
     

归并排序方法：

吐血编程啊，防着july写的，单写还真写不对

1 //归并排序方法，采用多路归并，没有任何要求，什么样都能拍还是稳定的，就是要多次读写文件  2 //要求1m内存，而10的7次方个int是40M，要分成40个文件，一个文件1M，25万的数组为1M  3 #include 
     
        4 using namespace std;  5 #include 
      
         6 #include 
       
          7 #include 
        
           8 #define size 10000000  9 #define onesize 250000 10  11 int readtomem(FILE * fp,int * space)         //读到内存时注意返回读了多少，最多到onesize单可能比那个小 12 { 13     int index=0; 14     while(index