［STL应用之使用 bitset 实现排序］

现在的位置: 首页 > 综合 > 正文

RSS

［STL应用之使用 bitset 实现排序］

2013年09月22日 ⁄ 综合 ⁄ 共 1130字 ⁄ 字号小中大 ⁄ 评论关闭

/××××××××××××××××××××××××××MonkeyAndy原创，转载请注明出处×××××××××××××××××××××××/

http://blog.csdn.net/MonkeyAndy

/××××××××××××××××××××××××××MonkeyAndy原创，转载请注明出处×××××××××××××××××××××××/

没有最好只有更好，如您有更好的解决方案，欢迎批评指正，共同学习进步

问题描述：

当有大量不重复的数据需要排序时，如n（n在 10^k , 32>k>7 ）时，采用常用的算法，一般需要开辟的辅助存储空间比较大，本文介绍采用STL中的bitset实现排序。

首先介绍下bitset

bitset为C++ STL中的一个库函数，使用时需要包含 #include <bitset>，本文仅介绍其在本文中用到的功能函数。

构造函数
bitset<n> b;
b有n位，每位都为0.参数n可以为一个表达式.
如bitset<5> b0;则"b0"为"00000";

set(pos)
把在pos处的二进制位置为1

reset()
把所有二进制位都置为0

有了以上函数便可以实现基本的排序了（注：对于有重复数据和负数数据的本方法不适用）。

思路：

1、创建一个有MAX个数据的bitset对象bit_map，将其所有位使用reset()置为0.

2、遍历所有数据，使用set()函数将数值对应的位置为1.

3、遍历bit_map中的所有位，若其值为1,则输出，亦即排序后的结果

demo

#include <iostream>
#include <bitset>
#include <ctime>
#include <cstdlib>
#include <iomanip>

using namespace std;

#define MAX 100
int main()
{
	bitset<MAX> bit_map;
	bit_map.reset();
	int count=0;
	srand(time(NULL));

	for(int i=0; i<MAX; i++)
	{
		int rd = rand() % 100;
		bit_map.set(rd);
	}

	for(int j=0; j<MAX; j++)
	{
		if(bit_map[j] == 1)
		{
			cout<< setw(12) << j << " ";

			if((count+1) % 10 == 0)
				cout << "\n";

			count++;
		}
	}

	cout << "\nTOTAL:  " << count << endl;

	return 0;

	
}