位图排序法

白羽扬 — Thu, 17 Sep 2009 02:48:00 GMT

位图排序法有两个限制条件：

1、待排序数据都在一个已知的相对较小的范围内；

2、所有数据没有重复；

位图排序法思想：假设待排序的所有数都小于1000万，那么使用一个具有1000万个位的字符串来表示这个待排序文件，其中，当且仅当整数i在文件中存在时，第i位置为1.具体实现是，定义一个整形数组，如 int order[10000000];然后将i作为数组下标将order[i]=1；最后再做个循环检查如果order[i]==1的，输出i。上代码：

1#include<iostream>
2#include<fstream>
3using namespace std;
4
5double random(double start,double end)
6{
7    return start+(end-start)*rand()/(RAND_MAX+1.0);
8}
9
10int main()
11{
12    int temp[50];
13    int order[50] = {0};
14    cout<<"数列:"<<endl;
15    for(int i = 0;i != 50;++i)
16    {
17        temp[i] = random(0,50);
18        cout<<temp[i]<<" ";
19    }
20    cout<<endl;
21    for(int j = 0;j != 50;++j)
22    {
23        order[temp[j]] = 1;
24    }
25    cout<<"位图:"<<endl;
26    for(int t = 0;t != 50;++t)
27    {
28        cout<<order[t]<<" ";
29    }
30    cout<<endl;
31    cout<<"排序后:";
32    for(int k = 0;k != 50;++k)
33    {
34        if(order[k]==1)
35    cout<<k<<" ";
36    }
37    cout<<endl;
38    return 0;
39}

白羽扬 2009-09-17 10:48 发表评论

C++博客-baiyuyang

位图排序法