sort-桶排序

佚名 6年前 (2019-04-11) 随笔 1721人围观抢沙发百度已收录

void list_insert(list<int> &t,int num)
{
    auto iter=t.begin();
    for(;iter!=t.end();++iter)
    {
        if(num<=*iter)
            break;
    }

    t.insert(iter,num);
}

void sort_bucket(vector<int> &v)
{
    int bucket_num=6;
    vector<list<int>> vlist=vector<list<int>>(bucket_num);

    int mix=v[0];
    int max=v[0];

    for(int i=1;i<v.size();i++)
    {
        if(v[i]>max) max=v[i];
        if(v[i]<mix) mix=v[i];
    }

    int space=(max-mix)/(bucket_num-1);
    for(int i=0;i<v.size();i++)
    {
        int index=(v[i]-mix)/space;
        list_insert(vlist[index],v[i]);
    }
    

    v.clear();
    for(int i=0;i<vlist.size();i++)
    {
        for(auto iter=vlist[i].begin();iter!=vlist[i].end();++iter)
            v.push_back(*iter);
    }
    
}