posts - 1, comments - 0, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

位图排序法

Posted on 2009-09-17 10:48 白羽扬 阅读(380) 评论(0)  编辑 收藏 引用
位图排序法有两个限制条件：
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}


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理