BitMap排序

问题描述：

      BitMap排序思想:

            用1bit位标记某个元素对应的值

      优点：

            效率高，不允许进行比较和移位

            占用内存少，比如32个整数，使用bit存储需要4byte，使用int数组需要32*4byte

     缺点：

           无法对重复数据进行排序和查找

    应用场景：

                ①：对10亿个不重复的整数进行排序。

                ②：找出10亿个数字中重复的数字。

 

算法实现：

/*
*    BitMap算法
*    思想：
*        用1bit位来标记某个元素对应的value，而key即是该元素。
*    
*    优点：
*        效率高，不允许进行比较和移位
*        占用内存少，比如32个整数，使用bit存储需要4byte数据存储，使用数组需要32byte
*
*    缺点：
*        无法对重复的数据进行排序和查找
*/

#ifndef BitMap_H
#define BitMap_H

using std::cout;
using std::endl;

#define ByteLength 8

//返回数组元素中的最大值
int getMax(int* array,int size)
{
    int max=array[0];
    for (int i=1;i<size;i++)
        max=array[i]>max?array[i]:max;
    return max;
}

//返回存储数组需要的byte个数
int getByteCount(int* array,int size)
{
    int max=getMax(array,size);
    int byteCount=max/ByteLength+1;    //BitMap存储该数组需要byteCount个字节
    return byteCount;
}

//返回存储整数对应的byte索引
int index(int data)
{
    return data/ByteLength;
}

//返回存储整数对应的byte偏移
int shift(int data)
{
    return data%ByteLength;
}

//BitMap排序
void  bitmapSort(int* array,char* byteArray,int size)
{
    int j=0;
    int k=0;
    for (int i=0;i<size;i++)
    {
        j=index(array[i]);
        k=shift(array[i]);
        byteArray[j] |= (char)(k>0?(1<<k):0);    //注意k为0的情况
    }
}

//输出byte位为1时对应的值
void getValue(char data,int index)
{
    if (data & 0x1==0)    //data为0的情况
    {
        cout<<index*ByteLength<<"	";
    }

    for (int i=0;i<ByteLength;i++)
    {
        if (data & (char)(1<<i))
            cout<<index*ByteLength+i<<"	";
    }
}

//输出排序后的数组
void print(char* array,int size)
{
    int count=0;
    for (int i=0;i<size;i++)
    {
        if (count>0 && count%10==0)
            cout<<endl;

        if (array[i]==0)
        {
            continue;
        }
        else
        {
            getValue(array[i],i);
            count++;
        }
    }
    cout<<endl;
}

#endif