C++排序算法之位图法排序

电玩女神 2022-06-12 02:55 178阅读 0赞

**位图法排序**

**（1）问题描述**

《编程珠玑》里有这样一个问题：

1.输入：一个至多包含1千万个非负整数的文件

2.特征：①每个数都是小于10000000的非负整数；②没有重复的数字；③数据之间不存在关联关系。

3.约束：①最多1MB的内存空间可用；②磁盘空间充足；③运行时间最多几分钟，最好是线性时间。

4.输出：按升序排列的整数序列。

由于待排的数据比较多，不是是相当的多，如果我们单纯的使用常见的排序方法时间效率会很低，运行时间很长很长，而且要求最多使用1M的内存空间。所以我们不能同时把所有的整数读入内存（如果每个整数使用7个字节来存储，那么1MB内存空间只能存大约143000个数字）。当然我们可以多次读取输入文件，多次排序，但是更好的方案是使用位图排序，可以使用有限的1MB内存空间并只进行一趟排序。

**（2）位图法**

位图法：bitmap，就是用每一位来存放某种状态，适用于大规模不重复的数据，通常用来判断某个数据是否存在。

举例来说明一下：

对unsigned且没有重复的数字进行排序，假设我们要对0-7内的6个元素（3,6,2,4,7,1）排序。我们采用Bitmap的方法来达到排序的目的。要表示8个数，我们只需要8个bit（1Bytes）。首先申请1bytes的空间，然后将所有的bit位全都置为0.

接着我们遍历这6个元素，首先第一个元素为3，那么就把3对应的位置设置为1.如下图（下标从0开始）

按照同样的方式处理所有的元素，最终的结果为：

最后，我们只需要遍历一遍bit区域，将1对应的位置的下标（1,2,3,4,6,7）输出，这样就达到了排序的目的。是不是很神奇呢？而且只需要开辟1bytes的空间就可以。

C++标准库提供了一个bitset容器，是一种位集合的数据结构，它让我们可以像使用数组一样使用位，可以访问指定下标的bit位，和其它容器一样，bitset也是一个模板类。下面我们就利用bitset容器实现简单的位图法排序。

代码实现如下：

#include <iostream>
    #include <bitset>
    #include <vector>
    using namespace std;
    
    const unsigned int max_num = 20000;		//最大数字
    
    void BitmapSort(vector<unsigned int>& R)
    {
    	bitset<max_num + 1> bit;
    	//遍历元素，将对应位置为1
    	for (auto x : R)
    		bit.set(x);					//bit.set(n)表示将第n位设为1
    	int j = 0;
    	//输出排序结果
    	for (int i = 0; i <= max_num; i++)
    		if (bit.test(i))				//bit.test(n)判断第n位是否为1
    			R[j++] = i;
    }
    
    int main()
    {
    	vector<unsigned int> R = { 3,6,2,4,7,1 };
    	BitmapSort(R);
    	for (auto x : R)
    		cout << x << " ";
    	cout << endl;
    }

扩展：

腾讯面试题

给40亿个不重复的unsigned int的整数，没有排过序，然后再给一个数，如果快速判断这个数是否在那40亿个数当中。

用位图法：40亿unsigned int，则用位图表示的话需要大小为40亿个bit=4\*10 9 bit=0.5\*10 9 bytes 因此申请的内存只需要大小约为512MB左右，这样在内存每个bit代表一个unsigned int整数，并将每个bit初始化为0，然后将40亿个unsigned int的整数读入，每个unsigned int的整数对应bit设置为1，读入后，最后看所给定的数对应的bit是否为1，是1存在，否则不存在。