我只是写了一个简单的迭代基数排序,我想知道我是否有正确的想法 .
递归实现似乎更常见 .
我正在排序4字节整数(unsigned以保持简单) .
我使用1字节作为'digit' . 所以我有2 ^ 8 = 256个桶 .
我先排序最重要的数字(MSD) .
在每次排序之后,我按照它们存在于存储桶中的顺序将它们放回到数组中,然后执行下一个排序 .
所以我最终做了4斗 .
它似乎适用于一小组数据 . 由于我这样做,MSD I 'm guessing that'不稳定,可能会因不同的数据而失败 .
我错过了什么专业吗?
#include <iostream>
#include <vector>
#include <list>
using namespace std;
void radix(vector<unsigned>&);
void print(const vector<list<unsigned> >& listBuckets);
unsigned getMaxForBytes(unsigned bytes);
void merge(vector<unsigned>& data, vector<list<unsigned> >& listBuckets);
int main()
{
unsigned d[] = {5,3,6,9,2,11,9, 65534, 4,10,17,13, 268435455, 4294967294,4294967293, 268435454,65537};
vector<unsigned> v(d,d+17);
radix(v);
return 0;
}
void radix(vector<unsigned>& data)
{
int bytes = 1; // How many bytes to compare at a time
unsigned numOfBuckets = getMaxForBytes(bytes) + 1;
cout << "Numbuckets" << numOfBuckets << endl;
int chunks = sizeof(unsigned) / bytes;
for(int i = chunks - 1; i >= 0; --i)
{
vector<list<unsigned> > buckets; // lazy, wasteful allocation
buckets.resize(numOfBuckets);
unsigned mask = getMaxForBytes(bytes);
unsigned shift = i * bytes * 8;
mask = mask << shift;
for(unsigned j = 0; j < data.size(); ++j)
{
unsigned bucket = data[j] & mask; // isolate bits of current chunk
bucket = bucket >> shift; // bring bits down to least significant
buckets[bucket].push_back(data[j]);
}
print(buckets);
merge(data,buckets);
}
}
unsigned getMaxForBytes(unsigned bytes)
{
unsigned max = 0;
for(unsigned i = 1; i <= bytes; ++i)
{
max = max << 8;
max |= 0xFF;
}
return max;
}
void merge(vector<unsigned>& data, vector<list<unsigned> >& listBuckets)
{
int index = 0;
for(unsigned i = 0; i < listBuckets.size(); ++i)
{
list<unsigned>& list = listBuckets[i];
std::list<unsigned>::const_iterator it = list.begin();
for(; it != list.end(); ++it)
{
data[index] = *it;
++index;
}
}
}
void print(const vector<list<unsigned> >& listBuckets)
{
cout << "Printing listBuckets: " << endl;
for(unsigned i = 0; i < listBuckets.size(); ++i)
{
const list<unsigned>& list = listBuckets[i];
if(list.size() == 0) continue;
std::list<unsigned>::const_iterator it = list.begin(); // Why do I need std here!?
for(; it != list.end(); ++it)
{
cout << *it << ", ";
}
cout << endl;
}
}
更新:
似乎在LSD形式中运行良好,可以通过更改基数中的块循环来修改它,如下所示:
for(int i = chunks - 1; i >= 0; --i)
2 回答
让我们看一下两位十进制数的例子:
按第一位数产生排序
接下来,按第二个数字排序,屈服
好像不对,不是吗?或者这不是你在做什么?如果我弄错了,也许你可以告诉我们代码 .
如果您对具有相同第一个数字的所有组执行第二次存储桶排序,则您的算法将等同于递归版本 . 它也会稳定 . 唯一的区别是你要对广告优先级进行排序,而不是深度优先 .
您还需要确保在重新组装之前将每个桶从MSD排序到LSD . 示例:19,76,90,34,84,12,72,38在MSD上分为10个桶[0-9] B0 = []; B1 = [19,12]; B2 = []; B3 = [34 ,38]; B4 = []; B5 = []; B6 = []; B7 = [76,72]; B8 = [84]; B9 = [90];如果你要重新组装然后再次排序它将无法正常工作 . 而是递归地对每个桶进行排序 . B1分为B1B2 = [12]; B1B9 = [19]一旦完成所有分类,您可以正确重组 .