编程珠玑 -- bitSort
＜C专家编程＞看完了。受益最大的应该就是对声明部分的理解吧，特别是函数指针什么的。通过函数指针，可以实现一个自动机。我是这么想的。另外就是因此而学会了使用vi进行编程。接下来想学写makefile文件，不然文件一多调试修改后又要重新编译好几个文件。
?
回到编程珠玑上。第一篇描述了这样一个问题：在一定的内存限定下（内存大概有1MB）对一个包含有K个小于n (n=10^7)的数据的文件进行排序，可以保证，这K个数据没有一个是重复的（其实就是电话号码）。
?
qsort只能对内存中的数据进行排序，也就是说，要对文件遍历40次，每次读取一定范围的数到内存中，然后进行排序。（如，第一次，读取0～249，999范围内的数据到内存，qsort后输出到新的文件，然后再从文件中读取250,000~499,999的数据。。）这样的话，必须对文件遍历40次。
?
mergeSort只读取一次源文件，但是要开辟很多个临时文件进行辅助排序。
?
有什么办法可以只读一次源文件，写一次output，又不需要临时文件的辅助呢？
?
这个问题有三个特征是一般排序问题不具备的：
1。 数据范围比较小（＜10^7）
2。 没有重复数据
3。 每个数据都很独立，没有其他相联的数据。
?
由于数据没有重复，同时所有数据都小于10^7，我们可以用每个bit来代表一个数据是否存在源文件中（由这些bit组成的表大概需要1.25MB），一边读取文件的时候一边设置相应的位，最后输出的时候检查相应的位是否为1，为1则输出该数字。如果内存严格要求1MB的话，可以分成两次读取。
?
我在实现的时候，写了三个函数，一个用于产生K个不重复的随机数，一个用于设置相应位，一个用于打印由map得到的排序后的结果。总之写了挺长的代码。。大概有100行了，后来看了后面的solution，不禁汗颜，，果然字字珠玑啊，10几行代码就把整个精华都写出来了，贴在这里给大家看看吧：
?
#define BITSPERWORD 32#define SHIFT 5#define MASK 0x1F#define N 10000000int a[1+N/BITSPERWORD];void set( int i ){ a[i>>SHIFT] |= (1<<(i&MASK)); }void clear( int i ){ a[i>>SHIFT] &= ~(1<<(i&MASK)); }int test( int i ){ return (a[i>>SHIFT] & (1<<(i&MASK))); }main(){int i=0;int j=0;for( i=0; i<N; i++ )clear(i);FILE* fp = fopen( "sortData", "r" );if( fp != NULL ){while( fscanf( fp, "%d", &i ) != EOF )set(i);for( i=N-1; i>=0; i-- ){if( test(i) ){j++;printf( "%d: %d\n", j, i );}}}}?
再看看我自己写的三个函数：
setMapAtK跟他的set基本是一样的，可是与起来远不如人家紧凑：
//这里考虑到我同时还要利用这个函数来产生不重复的随机数，所以选择了使用返回值int setMapAtK( int gen, int* map ){int num = gen >> 5;int bit = gen & 31;if( map[num] & (1 << (bit)))return 1;map[num] = map[num]|(1 << (bit));return 0;}?printMap就很悲惨了，不过可取的一点是，我是对每个整数进行的操作，当取完最后一个为1的位后该整数就为0，也就是说，没有必要再对这个整数后面的位了。对于稀松集，这样效率是会提高一点的。
void printMap( int* map ){int r = 1;int i=MAXINT_TEMP-1;int size = MAXINT_TEMP>>5;int left = MAXINT_TEMP & 31;//这里主要考虑到最大整数可能并不是32的整数（虽然在我们的例子中n=10^7是）if( left > 0 ){int j = left-1;unsigned int num = (1<<j);int t = map[size];while(j>=0 && t ){if( map[size]& num ){t = (t & (num^(0xFFFF)));printf( "%d: %d\n", r++, i );}j--;i--;num = (num>>1);}i -= (j+1);}int k;//这里是主要循环for( k=size-1; k>=0; k-- ){int j=32;unsigned int num = 0x80000000;int t = map[k];while( j && t ){if( map[k] & num ){t = (t& (num^(0xFFFFFFFF)));printf( "%d: %d\n", r++,i );}j--;i--;num = (num>>1);}i -= j;}}?试验的结果我的时间是要比它少5、6秒（k=10^6)，不过随着k逐渐增大，这样的优势自然就不存在了。