微软笔试题 给一个包含10^7个整数的大文件排序 (一)

这个题目有一个前提条件，大文件的中的数据有有一个特点，那就是不存在重复的数据。就算是重复的数据，也只让你求出去除重复之后的那些数据的排序结果。

如果题目变成了这样，我们就可以考虑创建一个大的数组。数组的下表表示一个整数，数组的内容在我遍历文件的时候再赋值。如果数组下标代表的那个整数存在，我们就把数组的这个元素赋值为1，否则赋值为0.这样我们就可以再次遍历数组，把元素的值为1的那些下标输出到另一个文件，这样另一个文件中就存放了排好序的数据了。

上面的那个数组，其实我们可以用vector,或者bitset;来实现，这就是所谓的位图算法，实现如下：

[cpp]
//对10^7个整数的文件进行排序，整数无重复，将排序的结果写到sorted_data.txt文件中。
//用位图的方法。
void sort_big_file_with_single_data()
{
timer t;
//生成一个大数集合，随机排列
const int n=5000000;
vector a;
for (int i=0;i a.push_back(i);

variate_generator > myrandom (mt19937(), uniform_int<>(0,n-1));
for (int i=0; i swap(a[myrandom()],a[myrandom()]);

//写数据到文件
ofstream fout("data.txt",ios::binary);
if (!fout)
{
cout<<"can not open file to write"< }
for (int i=0;i {
fout.write(reinterpret_cast(&a[i]),sizeof(int));
}
fout.close();




//从文件中读取前100个数据并显示
ifstream fin;
fin.open("data.txt",ios::binary);
for (int i=0,num=0;i<100;i++)
{
fin.read(reinterpret_cast(&num),sizeof(int));
if (fin.eof())
{
break;
}
cout< }
fin.close();


//对文件排序
bitset bit;
bit.reset();
//ifstream fin;
fin.open("data.txt",ios::binary);
int i=0;
while (true)
{
fin.read(reinterpret_cast(&i),sizeof(int));
if (fin.eof())
{
break;
}
bit[i]=true;
}
fin.close();
//将排序的文件输出到sorted_data.txt
//ofstream fout;
fout.open("sorted_data.txt",ios::binary);
for (int i=0;i {
if (bit[i]==true)
{
fout.write(reinterpret_cast(&i),sizeof(int));
}
}
fout.close();
cout<<"sort data "<

//读取已经排序的文件并显示前100个数据
fin.open("sorted_data.txt",ios::binary);
for (int i=0,num=0;i<100;i++)
{
fin.read(reinterpret_cast(&num),sizeof(int));
if (fin.eof())
{
break;
}
cout< }
fin.close();
}

//对10^7个整数的文件进行排序，整数无重复，将排序的结果写到sorted_data.txt文件中。
//用位图的方法。
void sort_big_file_with_single_data()
{
timer t;
//生成一个大数集合，随机排列
const int n=5000000;
vector a;
for (int i=0;i a.push_back(i);

variate_generator > myrandom (mt19937(), uniform_int<>(0,n-1));
for (int i=0; i swap(a[myrandom()],a[myrandom()]);

//写数据到文件
ofstream fout("data.txt",ios::binary);
if (!fout)
{
cout<<"can not open file to write"< }
for (int i=0;i {
fout.write(reinterpret_cast(&a[i]),sizeof(int));
}
fout.close();

//从文件中读取前100个数据并显示
ifstream fin;
fin.open("data.txt",ios::binary);
for (int i=0,num=0;i<100;i++)
{
fin.read(reinterpret_cast(&num),sizeof(int));
if (fin.eof())
{
break;
}
cout< }
fin.close();

//对文件排序
bitset bit;
bit.reset();
//ifstream fin;
fin.open("data.txt",ios::binary);
int i=0;
while (true)
{
fin.read(reinterpret_cast(&i),sizeof(int));
if (fin.eof())
{
break;
}
bit[i]=true;
}
fin.close();
//将排序的文件输出到sorted_data.txt
//ofstream fout;
fout.open("sorted_data.txt",ios::binary);
for (int i=0;i {
if (bit[i]==true)
{
fout.write(reinterpret_cast(&i),sizeof(int));
}
}
fout.close();
cout<<"sort data "<

//读取已经排序的文件并显示前100个数据
fin.open("sorted_data.txt",ios::binary);
for (int i=0,num=0;i<100;i++)
{
fin.read(reinterpret_cast(&num),sizeof(int));
if (fin.eof()