C中二进制表示的基排序算法

Question

在C中实现基数排序算法的最有效方法是什么，它根据二进制表示(在整数数组上)排序？

我希望能够给出一个数字n，表示要排序的元素数，并给出一个值b，说明在排序算法中您希望被解释为一位数的二进制数，这样您就可以根据数字的大小改变n和b。

对此有何建议？

Answer 1

对此有何建议？

#include <string.h>
#include <limits.h>

void radixsort(unsigned int array[], int n, int b)
{
    unsigned int place[n], *a0 = array, *a1 = place, *a;
    int values = 1<<b, start[values+1], bmask = values-1, shift;
    for (shift = 0; shift < sizeof (int) * CHAR_BIT; shift += b)
    {
        int i;
        memset(start, 0, sizeof start);
        for (i = 0; i < n; ++i) ++start[(a0[i]>>shift&bmask)+1];
        for (i = 2; i < values; ++i) start[i] += start[i-1];
        for (i = 0; i < n; ++i) a1[start[a0[i]>>shift&bmask]++] = a0[i];
        a = a0, a0 = a1, a1 = a;
    }
    if (a0 != array) memcpy(array, a0, sizeof place);
}

结果表明，rcgldr对该算法的描述符合此实现，只是在需要时才计算起始偏移量。

Answer 2

我使用的方法是对数据进行一次遍历，以创建用于排序的每个位字段中位模式出现次数的直方图集(矩阵)。这是基数排序的“计数”步骤。然后，将直方图转换为起始索引偏移量，方法是从零开始，并在直方图集中累积每个条目的计数之和。然后对每个位字段执行基排序，从最低到最高，使用与该位字段关联的起始索引，并在使用时递增每个索引。Wiki文章：

sort