一、主要思想
位图排序的思想就是在内存中申请一块连续的空间作为位图，初始时将位图的每一位都置为0，然后依次读取待排序文件的整数，将整数所在的位设置为1，最后扫描位图，如果某一位为1，则说明这个数存在，输出到已排序文件。比如待排序的数据S={3,0,4,1,7,2,5}，max(S)=7，我们可以设置一个八位的位图B，将位图的每一位初始为0，即B=[0,0,0,0,0,0,0,0]，对S中的每一个整数d，设置B[d]=1，即B=[1,1,1,1,1,1,0,1]，最后扫描位图，对位图的每一位i,如果B[i]==1，则输出i到已排序文件，排序后的S={0,1,2,3,4,5,7}。
整个过程只需要遍历一遍待排序文件和位图，时间复杂度O(n)，需要的辅助空间为(max(S)/8)B。虽然这个排序算法只能在无重复的整数集上运行，但对于有些需求，确实做到高效实现，比如说给手机号码排序，手机号码11位，第一位始终为1，理论上可以有10^10个号码，但一些号码未发放，即有些号码在系统中不存在，假设系统中有50%的合法号码，每个号码用long int表示，这么多号码所需要的空间为50%*(10^10)*4B=20GB，不能放在内存中进行快速排序。一个可选的方案是分多趟进行归并排序，但需要较长的时间。我们申请一个10^10位的位图，需要的内存是10^10/8B=1.25GB，完全可以在当代的PC机上运行，在扫描位图时，假设某一位i为1，输出文件时，在前面添加一个1，例如i=3885201314，输出为13885201314。
二、算法实现
用c语言实现的话，需要自己封装位图操作，这里需要用到三个操作：设置位图的所有位为0(setAllZero)；设定指定的位为1(setOne)；查看指定的位是否为1(find)；代码如下：
#include
#include
#include
#include
#include
#define MAX_NUM 16777216//最大的数,也就是需要的位
#define BYTE_NUM (1+MAX_NUM/8)//字节数
#define MASK 0x07
void setAllZero(unsigned char *p,long size);
void setOne(unsigned char *p,long loc);
int find(unsigned char *p,long loc);
bool getSorted(unsigned char *bitmap,char *fileName);
bool setBitmap(unsigned char *bitmap,char *fileName);
int bitmapSort();
int main(){
return bitmapSort();
}
int bitmapSort(){
unsigned char *bitmap; //位图指针
bitmap = (unsigned char *)malloc(BYTE_NUM*sizeof(unsigned char));
if(bitmap == NULL){
printf("Malloc failedn");
return -1;
}
setAllZero(bitmap,BYTE_NUM);//将位图所有位设置为0
setBitmap(bitmap,"phoneNumber.txt");//扫描待排文件，将位图对应位设置为1
getSorted(bitmap,"bitmapSort.txt"); //扫描位图，将位图为1的位号输出到文件
free(bitmap);//释放位图
return 0;
}
/***********设置待排序数据的位图**************/
bool setBitmap(unsigned char *bitmap,char *fileName){
FILE *readFp;
printf("Setting bitmap...n");
readFp = fopen(fileName,"r");
if(readFp == NULL)
return false;
long phoneNum=0;
while(fscanf(readFp,"%ldn",&phoneNum) != EOF){
setOne(bitmap,phoneNum);//将 phoneNum位设置为1
}
fclose(readFp);
return true;
}
/*****顺序遍历位图输出记录，从而实现排序****************/
bool getSorted(unsigned char *bitmap,char *fileName){
printf("Search bitmap...n");
FILE *writeFp;
writeFp = fopen(fileName,"w");
if(writeFp == NULL)
return false;
long phoneNum=0;
for(phoneNum = 0; phoneNum < MAX_NUM; phoneNum += 1){
if(find(bitmap,phoneNum)){
fprintf(writeFp,"%ldn",phoneNum);
}
}
fclose(writeFp);
return true;
}
/******先将位图清零********/
void setAllZero(unsigned char *bitmap,long size){
for(long i=0;i>3)相当于整除2^3=8，即定位到字节数，MASK=0x07,loc&MASK相当于loc%8
***************************************************/
void setOne(unsigned char *bitmap,long loc){
*(bitmap+(loc>>3)) |= (13))) & (1