位图法排序

分析：那么我们来看一个具体的例子，假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这里假设这些元素没有重复）。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数，我们就只需要8个Bit（1Bytes），首先我们开辟1Byte的空间，将这些空间的所有Bit位都置为0，如下图：

然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位置为1（可以这样操作：p+(i/8)|(0x01<<(i%8)）当然了这里的操作涉及到Big-ending和Little-ending的情况，这里默认为Big-ending）,因为是从零开始的，所以要把第五位置为一（如下图）：

接着再处理第二个元素7，将第八位置为1,，接着再处理第三个元素，一直到最后处理完所有的元素，将相应的位置为1，这时候的内存的Bit位的状态如下：

最后我们现在遍历一遍Bit区域，将该位是一的位的编号输出（2，3，4，5，7），这样就达到了排序的目的。

代码实现如下：

 1 /*****位图排序法**********/ 2  3 #include <memory.h> 4 #include <iostream.h> 5  6 #define BYTESIZE 8 7  8 void SetBit(unsigned char *data,int pos) 9 {10     for (int i=0;i<pos/BYTESIZE;i++)11     {12         data++;13     }14 15     *data=(*data)|(0x01<<(pos%BYTESIZE));16 }17 18 void BitmapSort(int data[],int n)19 {20     if (NULL==data || n<=0)21     {22         return;23     }24 25     int max=data[0];26     for (int i=1;i<n;i++)27     {28         if (data[i]>max)29         {30             max=data[i];31         }32     }33 34     int iByteNum=max/BYTESIZE+1;35 36     unsigned char *p=new unsigned char[iByteNum];37     unsigned char *q=p;38     memset(p,0,iByteNum);39     int *temp=new int[n];40     int num=0;41 42     for(i=0;i<n;i++)43     {44         SetBit(p,data[i]);45     }46     for (i=0;i<iByteNum;i++)47     {48         for (int j=0;j<BYTESIZE;j++)49         {50             if (((*p)&(0x1<<j))==(0x1<<j))51             {52                 temp[num]=i*BYTESIZE+j;53                 num++;54             }55         }56         p++;57     }58     memcpy(data,temp,sizeof(int)*n);59     delete []q;60     delete []temp;61 62 }63 64 void main()65 {66     int data[]={8,7,1,2,4,5,12,11,10};67     BitmapSort(data,9);68     for (int i=0;i<9;i++)69     {70         cout<<data[i]<<" ";71     }72 }