给10^7个数据量的磁盘文件进行排序

输入：给定一个文件，里面最多含有n个不重复的正整数（也就是说可能含有少于n个不重复正整数），且其中每个数都小于等于n，n=10^7。
输出：得到按从小到大升序排列的包含所有输入的整数的列表。
条件：最多有大约1MB的内存空间可用，但磁盘空间足够。且要求运行时间在5分钟以下，10秒为最佳结果。分析：下面咱们来一步一步的解决这个问题，
    1、归并排序。你可能会想到把磁盘文件进行归并排序，但题目要求你只有1MB的内存空间可用，所以，归并排序这个方法不行。
    2、位图方案。熟悉位图的朋友可能会想到用位图来表示这个文件集合。例如正如编程珠玑一书上所述，用一个20位长的字符串来表示一个所有元素都小于20的简单的非负整数集合，边框用如下字符串来表示集合

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

//位图方法，适用于无重复，有一定范围的排序
//从1到10^7个数排序
//500万是0.625M分成两次
#include <iostream>
#include <ctime>
#include <bitset>
#include <assert.h>
using namespace std;
char * filepath="unsort.txt";
char * filesort="sort.txt";
#define max_each 5000000
#define size 10000000

int num[size+1];
void createrandom()
{
     FILE *fp = fopen("unsort.txt", "w");  
    assert(fp);  
   int n;
    for ( n = 1; n <= size; n++)    
        //之前此处写成了n=0;n<size。导致下面有一段小程序的测试数据出现了0，特此订正。  
        num[n] = n;  
    srand((unsigned)time(NULL));  
    int i, j;  
  
    for (n = 0; n < size; n++)  
    {  
        i = (rand() * RAND_MAX + rand()) % 10000000;  
        j = (rand() * RAND_MAX + rand()) % 10000000;  
        swap(num[i], num[j]);  
    }  
  
    for (n = 1; n < size; n++)  
        fprintf(fp, "%d ", num[n]);  
    fclose(fp); 
}

    
int main()
{
    createrandom();
    clock_t begin=clock();
    bitset<max_each+1> bit;
    bit.reset();
    FILE * unsort_file=fopen(filepath,"r");
    assert(unsort_file);
    int num;
    while(fscanf(unsort_file,"%d ",&num)!=EOF)
    {
        if(num<=max_each)
            bit.set(num,1);

    }
    FILE * sort_file=fopen(filesort,"w");
    assert(sort_file);
    for(int i=1;i<=max_each;i++)
        if(bit[i]==1)
            fprintf(sort_file,"%d ",i);
    bit.reset();
    int result = fseek(unsort_file, 0, SEEK_SET);  
    if (result)  
        cout << "fseek failed!" << endl;  
    while(fscanf(unsort_file,"%d ",&num)!=EOF)
    {
        if(num>max_each)
        {
            num-=max_each;
            bit.set(num,1);
        }
    }
    for(int i=1;i<=max_each;i++)
        if(bit[i]==1)
            fprintf(sort_file,"%d ",i+max_each);
    clock_t end=clock();
    cout<<"finish and usetime=  "<<(end-begin)/CLK_TCK<<"s"<<endl;
    fclose(sort_file);
    fclose(unsort_file);
    system("pause");
}

归并排序方法：

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

//归并排序方法，采用多路归并，没有任何要求，什么样都能拍还是稳定的，就是要多次读写文件
//要求1m内存，而10的7次方个int是40M，要分成40个文件，一个文件1M，25万的数组为1M
#include <iostream>
using namespace std;
#include <ctime>
#include <assert.h>
#include <algorithm>
#define size 10000000
#define onesize 250000

int readtomem(FILE * fp,int * space)         //读到内存时注意返回读了多少，最多到onesize单可能比那个小
{
    int index=0;
    while(index<onesize&&fscanf(fp,"%d ",&space[index])!=EOF)
    {
        index++;
    }
    return index;
}

void writetofile(FILE * fp,int * space,int num)        //写的话是写多少个，返回空
{
    for(int index=0;index<num;index++)
        fprintf(fp,"%d ",space[index]);
}

string newfilename(int n)                         //起名字
{
    char na[128];
    sprintf(na,"data%d.txt",n);
    return na;
}

int  memsort()                                 //返回多少个文件
{
    int count=0;
    FILE * fp=fopen("unsort.txt","r");
    assert(fp);
    int * space=new int[onesize];
    while(true)
    {
        int read=readtomem(fp,space);
        if(read==0)
            break;
        sort(space,space+read);
        count++;
        string file=newfilename(count);
        FILE * fpout=fopen(file.c_str(),"w");         //file.c_str()将string转换成char *。
        assert(fpout);
        writetofile(fpout,space,read);
        fclose(fpout);
    }
    fclose(fp);
    delete[] space;                                                     //注意是delete[],而不是delete，前面有题写错了
    return count;
}

void merge_sort(int file_count)
{
    if(file_count<=0)
        return;
    FILE **file_array=new FILE*[file_count];                  //ＦＩＬＥ××
    assert(file_array);
    FILE * fp_result=fopen("memert_sort.txt","w");                      //fopen以w可以创建文件
    assert(fp_result);
    for(int i=0;i<file_count;i++)
    {
        string file=newfilename(i+1);　　　　　　　　　　　　　　　　//注意i+1
        file_array[i]=fopen(file.c_str(),"r");
    }
    bool *finish=new bool[file_count];
    int * result=new int[file_count];
    memset(finish,false,sizeof(bool)*file_count);
    for(int i=0;i<file_count;i++)
    {
        fscanf(file_array[i],"%d ",&result[i]);
    }
    while(true)
    {
        int index=0;
        while(index<file_count&&finish[index])        //判断退出条件，当finish全是true时，退出,跳过那些已经空的文件
            index++;
        if(index==file_count)
            break;
        int min=result[index];
        int min_index=index;
        for(int i=index+1;i<file_count;i++)
        {
            if(!finish[i]&&result[i]<min)                       //因为中间也有可能有空的，一般最后也有空的
            {
                min=result[i];
                min_index=i;
            }
        }
        fprintf(fp_result,"%d ",min);
        if(fscanf(file_array[min_index],"%d ",&result[min_index])==EOF)
        {
            finish[min_index]=true;
        }
    }
    fclose(fp_result);
    delete []finish;
    delete []result;
    for (int i = 0; i < file_count; i++)  
        fclose(file_array[i]);  
    delete [] file_array;  
}

int main()  
{  
    clock_t start_memory_sort = clock();  
    int aux_file_num = memsort();  
    clock_t end_memory_sort = clock();  
    cout << "The time needs in memory sort: " << end_memory_sort - start_memory_sort << endl;  
    clock_t start_merge_sort = clock();  
    merge_sort(aux_file_num);  
    clock_t end_merge_sort = clock();  
    cout << "The time needs in merge sort: " << end_merge_sort - start_merge_sort << endl;  
    system("pause");  
    return 0;  
}