首页 > 代码库 > BitSort

BitSort

2024-08-26 00:43:44   220人阅读

这个题为《编程珠玑》中提到的算法，解题思路和桶排序/基数排序一样，适用于大量没有重复的数据。

结题思路：

　　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


联系
我们