用位图排序

原 作者 李高晋 | 发表于 | 分类于 2017级

问题引入：如何给一个磁盘文件排序

  • 输入：一个最多包含n个正整数的文件，每个都小于n，其中n=10^7。如果在输入文件中有任何整数重复出现就是致命错误。没有其他数据与该整数相关联。
  • 输出：按照升序排列的输入整数的列表。
  • 约束：最多有（大约）1MB的内存空间可用，有充足的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化了。

实现概要

可用一个20位长的字符串来表示一个所有元素都小于20的简单的非负数集合。例如，可以用如下字符串来表示集合{1,2,3,5,8,13}：

0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0
  • 可分为三个自然阶段来编写程序
  1. 将所有的位置都置为0，将集合初始化为空
  2. 通过读入文件中的每个整数来建立集合，将每个对应的位置都置为1
  3. 检验每一位，如果该位为1，就输出对应的整数，由此产生有序的输出文件
/*第一阶段
for i = [0,n]
	bit[i] = 0
/*第二阶段
for each i in the input file
	bit[i] = 1
/*第三阶段
for i = [0,n]
 	if bit[i] == 1
 		write i on the output file
 //for i = [0,n]表示在0至n-1范围内进行迭代

具体实现的代码

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];

void set(int i){		a[i>>SHIFT] |=  (1<<(i & MASK)); )
void cle(int i){		a[i>>SHIFT] &= ~(1<<(i & MASK)); )
void test(int i){return a[i>>SHIFT] & 	(1<<{i & MASK)); )

main函数

int main()
{
	int i;
	for(i = 0; i < N ;i++)
		clr(i);
	while(scanf("%d", &i) != EOF)
		set(i);
	for(i = 0; i < N; i++)
		if(test(i))
			printf("%d\n", i);
	return 0;
}