排序文件中的N个不重复的正整数-白红宇

From 《编程珠玑》：一个文件中至多包含n个不重复的正整数，每个正整数都小于n，这里n=10^7。要求：以增量的形式输出经排序后的整数(限用1M内存)。

思路1：1M内存大约可以存储250000个整数。因此我们可以对输入文件遍历40次，第一次遍历过程中将值大于0、小于249999的所有整数读入内存，然后进行快速排序，再写入目标文件；第二次遍历过程中将值大于250000、小于499999的所有整数读入内存，排完序后写入目标文件，后面依此类推；第40次遍历过程中将大于9750000、小于9999999的所有整数读入内存，排完序后写入目标文件。此时目标文件中的整数已按增量排完序，顺序输出即可。

思路2：系统排序

(Command命令行)>sort originalFileName.ext >> targetFileName.ext

思路3：位图数据结构。

#define

bitSperWord 32

#define

shift 5

#define

mask 0x1f

#define

N 10000000

int

bitSperWord];

void

set

(

int

{a[i>>shift] |= (1<<(i & mask));}

void

clr(

int

{a[i>>shift] &=~(1<<(i & mask));}

int

test(

int

{

return a[i>>shift] & (1<<(i & mask));}

如果不限内存，还可以使用下面两种排序方法：

思路1：C++/STL

int

mail(

void

)

{

set<int> s;

int i;

set<int>::iterator j;

while(cin>>i)

s.insert(i);

for(j=s.begin();j!=s.end();++j)

cout<<*j<<" ";

return 0;

}

思路2：C/qsort

int

intcomp(

int

{

return *x-*y;

}

int

10000000

];

int

main(

void

)

{

int i,n=0;

while(scanf("%d",&a[n])!=EOF)

n++;

qsort(a,n,sizeof(int),intcomp);

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

printf("%d" ",a[i]);

}

本文转自Silent Void博客园博客，原文链接：http://www.cnblogs.com/happyhippy/archive/2006/12/19/601300.html，如需转载请自行联系原作者