博客位图排序源码

bitsort.cc

void BitSort(FILE *fp,const int num,FILE *fout)
{
    if(fp==NULL||num<=0) return;
    rewind(fp);

    boost::dynamic_bitset<> bitmap(UINT_MAX);
    std::unordered_map<unsigned int,unsigned int> count;

    bitmap.reset();
    unsigned int a;
    for(int i=0;i<num;++i){
        fscanf(fp,"%u",&a);
        if(!bitmap[a])
            bitmap.set(a,true);
        else
            count[a]++;//少一次
    }
    std::unordered_map<unsigned int,unsigned int>::iterator pos;
    for(long i=bitmap.size()-1;i>=0;--i){//避免无符号数不能退出循环
        if(bitmap[i]){//test output;
            fprintf(fout,"%12u",(unsigned int)i);//强制转型
            if((pos = count.find(i))!=count.end()){
                for(unsigned int t=0;t<pos->second;++t){
                    fprintf(fout,"%12u",i);
                }
            }
        }
    }
}

bulbswitch.cc

int bulbSwitch)int n){
    if(n<=0) return 0;
    boost::dynamic_bitset<> map(n);
    int i,j;
    for(j=1;j<=n;++j){
        for(i=j;i<=n;++i){
            if(i%j==0) map.flip(i-1);
        }
    }
    return map.count();
}

hashsort.cc

void HashSort(FILE *fp,int num,FILE *fout)
{
    if(fp==NULL) return;
    rewind(fp);

    multiset<unsigned int> v;
    unsigned int a;
    for(int i=0;i<num;++i){
        fscanf(fp,"%u",&a);
        v.insert(a);
    }
    for(auto it=v.rbegin();it!=v.rend();++it){
        fprintf(fout,"%12u",*it);
    }
}

quicksort.cc

void QuickSort(FILE *fp,int num,FILE *fout)
{
    if(fp==NULL||num<=0) return;
    rewind(fp);

    vector<unsigned int> v(num,0);//预先分配位置,提高速度
    unsigned int a;
    for(int i=0;i<num;++i){
        fscanf(fp,"%u",&a);
        v[i]=a;
    }
    std::sort(v.begin(),v.end(),std::greater<unsigned int>());
    for(auto it=v.begin();it!=v.end();++it){
        fprintf(fout,"%12u",*it);
    }
}