使用C++的基数排序

Question

假设我有一堆数字。我必须先将最不重要的数字放入相应的桶中。例如：530，我得先放入桶0。61号，我必须投入桶1.

我计划用一个多维数组来做到这一点。所以，我创建了一个2-dimenional阵列，这是NROWS 10（0〜9）和ncolumns是999999（因为我不知道怎么会大名单定）：

int nrows = 10; 
    int ncolumns = 999999; 

    int **array_for_bucket = (int **)malloc(nrows * sizeof(int *)); 
     for(i = 0; i < nrows; i++) 
      array_for_bucket[i] = (int *)malloc(ncolumns * sizeof(int)); 

    left = (a->value)%10; 
    array_for_bucket[left][?? ] = a->value; 

然后，我创建了一个节点打个电话。在这个节点a中，存在一个值50.为了找出我想要放入哪个桶，我计算“左”，并得到0.所以我想把这个a->值放入桶0中。但是现在我我卡住了。我该如何把这个价值放入桶中？我必须使用指针数组来做到这一点。

我想了很长时间，但还是没能找到一个很好的办法做到这一点。所以请与我分享一些想法。谢谢！

Answer 1

有一个更简单的方法来做到这一点，而不是radix*nkeys空间，你只需要一个nkeys大小的缓冲区。

分配可以容纳nkeys密钥的第二缓冲器中。现在，先对您的数据进行第一遍处理，然后简单计算每个存储桶中有多少个密钥。您现在可以创建一个大小为radix的指针数组，其中每个指针指向输出缓冲区中该存储桶的起始位置。最后，第二遍通过数据移动键。每次移动一个键时，增加该桶指针。

下面是一些C代码，使之成为C++：

void radix_sort(int *keys, int nkeys) 
{ 
    int *shadow = malloc(nkeys * sizeof(*keys)); 

    int bucket_count[10]; 
    int *bucket_ptrs[10]; 
    int i; 

    for (i = 0; i < 10; i++) 
     bucket_count[i] = 0; 

    for (i = 0; i < nkeys; i++) 
     bucket_count[keys[i] % 10]++; 

    bucket_ptrs[0] = shadow; 
    for (i = 1; i < 10; i++) 
     bucket_ptrs[i] = bucket_ptrs[i-1] + bucket_count[i-1]; 

    for (i = 0; i < nkeys; i++) 
     *(bucket_ptrs[keys[i] % 10]++) = keys[i]; 

    //shadow now has the sorted keys 

    free(shadow); 
} 

但我可能误解了这个问题。如果你正在做一些与基数不同的事情，请加一些细节。

Answer 2

，如果你想存储指针看看了Boost Pointer containers库。

Answer 3

C++是不是我的强项，但是从wikipedia-Raidx Sort这个代码是非常全面的，可能更多的是C++ - ISH比到目前为止你已经实现了什么。希望它可以帮助

Answer 4

这是C++，我们不使用malloc了。我们使用容器。二维数组是向量的向量。

vector<vector<int> > bucket(10); 
left = (a->value)%10; 
bucket[left].push_back(a->value);