首页 > 代码库 > BitSort
BitSort
这个题为《编程珠玑》中提到的算法,解题思路和桶排序/基数排序一样,适用于大量没有重复的数据。
结题思路:
1.遍历整个数据文件,每提取一个数据,在BitMap中对应的位置赋1
2.遍历BitMap的每一位,为1的位置上输出其再BitMap中的坐标
1 #include <iostream> 2 #include <fstream> 3 using namespace std; 4 const int maxnum=10000000; //设置位图大小 5 const int mask=0x1f; //求余 6 void setbit(int *a,int tmp); 7 int check(int *a,int tmp); 8 int main() 9 { 10 int bit[maxnum/32+1]; 11 for(int i=0;i<maxnum/32+1;i++) 12 bit[i]=0; 13 ifstream fin; 14 ofstream fout; 15 int tmp; 16 fin.open("test.txt"); 17 fout.open("result.txt"); 18 fin>>tmp; 19 while(tmp!=-1) 20 { 21 setbit(bit,tmp); 22 fin>>tmp; 23 } 24 for(int i=0;i<maxnum;i++) 25 { 26 if(check(bit,i)) 27 { 28 cout<<i<<endl; 29 fout<<i<<endl; 30 } 31 } 32 fin.close(); 33 fout.close(); 34 cout<<"end!"; 35 return 0; 36 } 37 void setbit(int *a,int tmp) 38 { 39 a[tmp>>5]|=(1<<(tmp&mask)); 40 } 41 int check(int *a,int tmp) 42 { 43 return a[tmp>>5]&(1<<(tmp&mask)); 44 }
BitSort
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。