0

假设我有一堆数字。我必须首先将最低有效数字放入相应的存储桶中。例如： 530 ，我必须先放入 0 号桶。对于 61 号，我必须放入 1 号桶。

我计划使用多维数组来做到这一点。所以我创建了一个二维数组，它的 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。在这个节点a中，有一个值50。为了找出我想把它放在哪个桶里，我计算了“左”，我得到了0。所以我想把这个a->值放到桶0里。但是现在我我被困住了。如何将此值放入存储桶中？我必须使用指针数组来做到这一点。

想了很久，还是没有找到好的办法。所以请和我分享一些想法。谢谢你！

4

4 回答 4

1

有一种更简单的方法可以做到这一点，而不是radix*nkeys空间，您只需要一个 nkeys-sized 缓冲区。

分配可以容纳nkeys键的第二个缓冲区。现在对您的数据进行第一次遍历，并简单地计算每个存储桶中最终有多少键。您现在可以创建一个radix-size 的指针数组，其中每个指针都指向输出缓冲区中该存储桶的开头。最后，第二次通过数据移动键。每次移动键时，都会增加存储桶指针。

下面是一些要制作成 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);
}

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

于 2012-03-04T23:32:27.807 回答
0

如果要存储指针，请查看 Boost Pointer 容器库。

于 2012-03-04T23:36:52.707 回答
0

C++ 不是我的强项，但来自wikipedia-Raidx Sort的这段代码非常全面，可能比你迄今为止实现的更接近 C++。希望能帮助到你

于 2012-03-04T23:38:19.970 回答
-1

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

vector<vector<int> > bucket(10);
left = (a->value)%10;
bucket[left].push_back(a->value);
于 2012-03-05T03:08:08.707 回答