纯整型排序的思考

2015/4/9周四　　

　　今天看编程珠玑，发现了个有趣的问题，大概是这样的：磁盘上有个文件，其中有多达1千万个不重复的整数（每个整数是7位数的，即小于10 000 000），如何排序后输出到硬盘？要求：时间大概10秒之内，内存大概1M。

　　分析：int 占4个字节，即32位，1 M = 1024 K = 1048576 byte，而1M / 4 byte = 262 144 个号码。明显不够用。那么考虑位图法，用1千万个位来表示，需要1250000个字节，约1200K，约1.17M。这样就大概满足了要求了，开始编码：

1 //初始化
2 memset(bit,0,sizeof(bit))
3 //磁盘读进内存
4 for(int i=0;i<n;i++)
5     bit[i]=0
6 //输出
7 for( i=0;i<n;i++)
8     write_to_file;

sort_for_int

　　具体实现位操作(自己写出来才能看懂代码)：

 1 #define BITSPERWORD 32 
 2 #define SHIFT 5 //位移量
 3 #define MASK 0x1F //右5位，代表32位
 4 #define N 10000000
 5 int a[1 + N/BITSPERWORD];
 6 
 7 void set(int i)
 8 {
 9     a[ i>>SHIFT ] |= ( 1<<(i & MASK) );
10 }
11 void clr(int i)
12 {
13     a[ i>>SHIFT ] &= ~( 1<<(i & MASK) );
14 }
15 int test(int i)
16 {
17     return a[ i>>SHIFT ] & ( 1<<(i & MASK) );
18 }

for_control